mersenneforum.org Calculator that can factor and find exact roots of polynomials
 Register FAQ Search Today's Posts Mark Forums Read

 2020-11-30, 17:15 #34 alpertron     Aug 2002 Buenos Aires, Argentina 22×3×112 Posts I should add TEX output to my calculators when requested by user. That would be an interesting addition to the programs.
 2020-12-13, 21:06 #35 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·112 Posts 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: $\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}$ 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.
 2020-12-25, 18:21 #36 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·112 Posts 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.
2020-12-25, 18:54   #37
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

62516 Posts

Quote:
 Originally Posted by alpertron 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

 2020-12-25, 19:05 #38 alpertron     Aug 2002 Buenos Aires, Argentina 22×3×112 Posts You are right. But the Eisenstein criterion cannot be used for all polynomials. There is still more room for optimization.
2021-03-02, 01:53   #39
alpertron

Aug 2002
Buenos Aires, Argentina

22×3×112 Posts

Quote:
 Originally Posted by R. Gerbicz 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.

 2022-06-02, 12:21 #40 alpertron     Aug 2002 Buenos Aires, Argentina 22×3×112 Posts I've just uploaded to the Web server a new version of the polynomial root calculator. Now it can compute the exact roots of quintic equations when the Galois group is 5 (all five roots are real). In this case trigonometric functions are required if we do not want to use complex numbers. Example: $x^{5} + x^{4} - 4x^{3} - 3x^{2} + 3x + 1 = 0$ $\bullet\,\,x_{1} = \frac{1}{-5} + \frac{2}{5}\sqrt{11}\left(\cos{\left(\frac{1}{5}\arccos\left(\frac{-89}{484}\sqrt{11} + \frac{25}{484}\sqrt{55}\right)\right) + \cos{\left(\frac{1}{5}\left(4\pi + \arccos\left(\frac{-89}{484}\sqrt{11} - \frac{25}{484}\sqrt{55}\right)\right)\right)\right)$ $\bullet\,\,x_{2} = \frac{1}{-5} + \frac{2}{5}\sqrt{11}\left(\cos{\left(\frac{1}{5}\left(2\pi + \arccos\left(\frac{-89}{484}\sqrt{11} + \frac{25}{484}\sqrt{55}\right)\right)\right) + \cos{\left(\frac{1}{5}\arccos\left(\frac{-89}{484}\sqrt{11} - \frac{25}{484}\sqrt{55}\right)\right)\right)$ $\bullet\,\,x_{3} = \frac{1}{-5} + \frac{2}{5}\sqrt{11}\left(\cos{\left(\frac{1}{5}\left(4\pi + \arccos\left(\frac{-89}{484}\sqrt{11} + \frac{25}{484}\sqrt{55}\right)\right)\right) + \cos{\left(\frac{1}{5}\left(6\pi + \arccos\left(\frac{-89}{484}\sqrt{11} - \frac{25}{484}\sqrt{55}\right)\right)\right)\right)$ $\bullet\,\,x_{4} = \frac{1}{-5} + \frac{2}{5}\sqrt{11}\left(\cos{\left(\frac{1}{5}\left(6\pi + \arccos\left(\frac{-89}{484}\sqrt{11} + \frac{25}{484}\sqrt{55}\right)\right)\right) + \cos{\left(\frac{1}{5}\left(2\pi + \arccos\left(\frac{-89}{484}\sqrt{11} - \frac{25}{484}\sqrt{55}\right)\right)\right)\right)$ $\bullet\,\,x_{5} = \frac{1}{-5} + \frac{2}{5}\sqrt{11}\left(\cos{\left(\frac{1}{5}\left(8\pi + \arccos\left(\frac{-89}{484}\sqrt{11} + \frac{25}{484}\sqrt{55}\right)\right)\right) + \cos{\left(\frac{1}{5}\left(8\pi + \arccos\left(\frac{-89}{484}\sqrt{11} - \frac{25}{484}\sqrt{55}\right)\right)\right)\right)$ You can select Pari-GP output and check using that tool that the formulas generated by the solver are correct.

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil Information & Answers 9 2018-04-17 18:18 fivemack Computer Science & Computational Number Theory 2 2015-09-18 12:54 Drdmitry Computer Science & Computational Number Theory 18 2015-09-10 12:23 geoff Factoring 5 2004-09-29 20:14 dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 12:36.

Thu Jun 30 12:36:23 UTC 2022 up 77 days, 10:37, 0 users, load averages: 1.64, 1.76, 1.81