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 101010001002 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·337 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·337 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

1,459 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 25048 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×337 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.

 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 04:43.

Tue Apr 20 04:43:41 UTC 2021 up 11 days, 23:24, 0 users, load averages: 2.03, 2.46, 2.71