mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2020-11-30, 17:15   #34
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default

I should add TEX output to my calculators when requested by user. That would be an interesting addition to the programs.
alpertron is offline   Reply With Quote
Old 2020-12-13, 21:06   #35
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×337 Posts
Default

I've just added TeX output to my polynomial factorization calculator located at https://www.alpertron.com.ar/POLFACT.HTM

For example, the roots of x17 + 1 are:

[math]\begin{array}{l}
\bullet\,\,x_{1} = -1\\
\bullet\,\,x_{2} = \cos{\frac{\pi }{17}} + i \sin{\frac{\pi }{17}} = \frac{1}{16}\left(1-\sqrt{17}+\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34-2\sqrt{17}-2\sqrt{34-2\sqrt{17}}-4\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{3} = \cos{ \frac{3\pi }{17}} + i \sin{\frac{3\pi }{17}} = \frac{1}{16}\left(1+\sqrt{17}+\sqrt{34+2\sqrt{17}}+2\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34+2\sqrt{17}-2\sqrt{34+2\sqrt{17}}-4\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{4} = \cos{ \frac{5\pi }{17}} + i \sin{\frac{5\pi }{17}} = \frac{1}{16}\left(1+\sqrt{17}+\sqrt{34+2\sqrt{17}}-2\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34+2\sqrt{17}-2\sqrt{34+2\sqrt{17}}+4\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{5} = \cos{ \frac{7\pi }{17}} + i \sin{\frac{7\pi }{17}} = \frac{1}{16}\left(1+\sqrt{17}-\sqrt{34+2\sqrt{17}}+2\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34+2\sqrt{17}+2\sqrt{34+2\sqrt{17}}+4\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{6} = \cos{ \frac{9\pi }{17}} + i \sin{\frac{9\pi }{17}} = -\frac{1}{16}\left(-1+\sqrt{17}+\sqrt{34-2\sqrt{17}}-2\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34-2\sqrt{17}+2\sqrt{34-2\sqrt{17}}+4\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{7} = \cos{ \frac{11\pi }{17}} + i \sin{\frac{11\pi }{17}} = -\frac{1}{16}\left(-1-\sqrt{17}+\sqrt{34+2\sqrt{17}}+2\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34+2\sqrt{17}+2\sqrt{34+2\sqrt{17}}-4\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{8} = \cos{ \frac{13\pi }{17}} + i \sin{\frac{13\pi }{17}} = -\frac{1}{16}\left(-1+\sqrt{17}-\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34-2\sqrt{17}-2\sqrt{34-2\sqrt{17}}+4\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{9} = \cos{ \frac{15\pi }{17}} + i \sin{\frac{15\pi }{17}} = -\frac{1}{16}\left(-1+\sqrt{17}+\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}\right) + \frac{i}{8}\sqrt{34-2\sqrt{17}+2\sqrt{34-2\sqrt{17}}-4\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{10} = \cos{ \frac{19\pi }{17}} + i \sin{\frac{19\pi }{17}} = -\frac{1}{16}\left(-1+\sqrt{17}+\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34-2\sqrt{17}+2\sqrt{34-2\sqrt{17}}-4\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{11} = \cos{ \frac{21\pi }{17}} + i \sin{\frac{21\pi }{17}} = -\frac{1}{16}\left(-1+\sqrt{17}-\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34-2\sqrt{17}-2\sqrt{34-2\sqrt{17}}+4\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{12} = \cos{ \frac{23\pi }{17}} + i \sin{\frac{23\pi }{17}} = -\frac{1}{16}\left(-1-\sqrt{17}+\sqrt{34+2\sqrt{17}}+2\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34+2\sqrt{17}+2\sqrt{34+2\sqrt{17}}-4\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{13} = \cos{ \frac{25\pi }{17}} + i \sin{\frac{25\pi }{17}} = -\frac{1}{16}\left(-1+\sqrt{17}+\sqrt{34-2\sqrt{17}}-2\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34-2\sqrt{17}+2\sqrt{34-2\sqrt{17}}+4\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}}\\
\bullet\,\,x_{14} = \cos{ \frac{27\pi }{17}} + i \sin{\frac{27\pi }{17}} = \frac{1}{16}\left(1+\sqrt{17}-\sqrt{34+2\sqrt{17}}+2\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34+2\sqrt{17}+2\sqrt{34+2\sqrt{17}}+4\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{15} = \cos{ \frac{29\pi }{17}} + i \sin{\frac{29\pi }{17}} = \frac{1}{16}\left(1+\sqrt{17}+\sqrt{34+2\sqrt{17}}-2\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34+2\sqrt{17}-2\sqrt{34+2\sqrt{17}}+4\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{16} = \cos{ \frac{31\pi }{17}} + i \sin{\frac{31\pi }{17}} = \frac{1}{16}\left(1+\sqrt{17}+\sqrt{34+2\sqrt{17}}+2\sqrt{17-3\sqrt{17}-\sqrt{170-38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34+2\sqrt{17}-2\sqrt{34+2\sqrt{17}}-4\sqrt{17-3\sqrt{17}+\sqrt{170-38\sqrt{17}}}}\\
\bullet\,\,x_{17} = \cos{ \frac{33\pi }{17}} + i \sin{\frac{33\pi }{17}} = \frac{1}{16}\left(1-\sqrt{17}+\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}+\sqrt{170+38\sqrt{17}}}\right)-\frac{i}{8}\sqrt{34-2\sqrt{17}-2\sqrt{34-2\sqrt{17}}-4\sqrt{17+3\sqrt{17}-\sqrt{170+38\sqrt{17}}}}\\
\end{array}[/math]

I had to change a lot of code to do this, so it is possible that there are some errors. So I will appreciate if you post here the error(s) you can find.
alpertron is offline   Reply With Quote
Old 2020-12-25, 18:21   #36
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default

I've just added FFT for modular polynomial multiplications when the modulus is small. This enables faster factoring when trying to factor integer polynomials, especially when the number of modular factors is small.

For example, the time required for indicating that x900 + 2 is irreducible changed from 12 seconds to 4.7 seconds.

At this moment the bottleneck is the division of polynomials. It appears that I have to implement a divide-and-conquer approach.
alpertron is offline   Reply With Quote
Old 2020-12-25, 18:54   #37
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101100112 Posts
Default

Quote:
Originally Posted by alpertron View Post
For example, the time required for indicating that x900 + 2 is irreducible changed from 12 seconds to 4.7 seconds.
That is way slower than my brain, it is irreducible with Eisenstein's criterion using p=2, ref:
https://en.wikipedia.org/wiki/Eisenstein%27s_criterion
R. Gerbicz is offline   Reply With Quote
Old 2020-12-25, 19:05   #38
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×337 Posts
Default

You are right. But the Eisenstein criterion cannot be used for all polynomials.

There is still more room for optimization.
alpertron is offline   Reply With Quote
Old 2021-03-02, 01:53   #39
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

54416 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Try x^720-1. On an older Chrome it is just crashing, on Firefox after some computation it has given: "index out of bounds", the 2nd run is still computing and it is in the: "Computing LLL in matrix of 43 × 43."
There were several buffer overflows that I've just fixed during this week. Now it works.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a arbitrary precision Calculator online that can handle this # ONeil Information & Answers 9 2018-04-17 18:18
On polynomials without roots modulo small p fivemack Computer Science & Computational Number Theory 2 2015-09-18 12:54
How to find values of polynomials with nice factorization? Drdmitry Computer Science & Computational Number Theory 18 2015-09-10 12:23
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 05:05.

Tue Apr 20 05:05:55 UTC 2021 up 11 days, 23:46, 0 users, load averages: 3.50, 3.09, 2.80

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.