Calculator that can factor and find exact roots of polynomials

[alpertron]

I should add TEX output to my calculators when requested by user. That would be an interesting addition to the programs.

[alpertron]

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 x¹⁷ + 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]

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 x⁹⁰⁰ + 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.

[R. Gerbicz]

Originally Posted by alpertron

For example, the time required for indicating that x⁹⁰⁰ + 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

[alpertron]

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

There is still more room for optimization.