Calculator that can factor and find exact roots of polynomials

[alpertron]

I've fixed several errors, including the number of digits in groups, a fix on biquadratic equations, now it works on Web browsers that do not support WebAssembly and other minor errors.

With respect to the equation mentioned by Dr Sardonicus, I fixed a few errors, but the support from the application is incomplete when the Galois group has order 5. I will continue working on this.

[ewmayer]

Thanks, Dario! That works even on my old FF-for-Mac-OS-10.6.8.

Was it much work to remove the WebAs dependence? I always say, if you can gain a lot of portability without having to expend inordinate effort, it's worth doing. But then again, I'm an old-timer - I realize much of the New Economy is based on domain fragmentation, getting folks to pay multiple times for what is basically the same thing. :)

[alpertron]

Originally Posted by ewmayer

Thanks, Dario! That works even on my old FF-for-Mac-OS-10.6.8.

Was it much work to remove the WebAs dependence? I always say, if you can gain a lot of portability without having to expend inordinate effort, it's worth doing. But then again, I'm an old-timer - I realize much of the New Economy is based on domain fragmentation, getting folks to pay multiple times for what is basically the same thing. :)

Thanks for testing. Actually, it detects whether the Web browser supports WebAssembly or not, so in the second case it uses asm.js (which is a subset of JavaScript that can be executed efficiently in the Web browser).

All my Web applications use WebAssembly because it runs 2 to 3 times faster than asm.js. This is important when you try to factor a big polynomial (or big number in https://www.alpertron.com.ar/ECM.HTM).

[alpertron]

Hello folks,

I have added more features to this calculator at https://www.alpertron.com.ar/POLFACT.HTM

Now it quickly factors integer polynomials with degree up to 1000 using Van Hoeij algorithm (which includes LLL), but notice that with some big polynomials it is possible to get an out of memory bounds so the factorization cannot complete.

Then it shows the roots of polynomials with degree up to 5 with radicals and trigonometric functions. Notice that the roots of most fifth-degree polynomials cannot be expressed with radicals or trigonometric functions. It also shows the roots of cyclotomic polynomials (x^n - 1 and their divisors) and polynomials of the form ax^n + b and ax^(2n) + bx + c.

For example, one of the roots of x^51 - 1 found by this calculator is:

x44 = cos(80*pi/51) + i * sin(80*pi/51) = -(1/32)*(-1+17^(1/2)-(34-2*17^(1/2))^(1/2)+2*(17+3*17^(1/2)+(170+38*17^(1/2))^(1/2))^(1/2)) + (1/16)*(3)^(1/2)*(34-2*17^(1/2)-2*(34-2*17^(1/2))^(1/2)+4*(17+3*17^(1/2)-(170+38*17^(1/2))^(1/2))^(1/2))^(1/2)-(i/32)*(3)^(1/2)*(-1+17^(1/2)-(34-2*17^(1/2))^(1/2)+2*(17+3*17^(1/2)+(170+38*17^(1/2))^(1/2))^(1/2))-(i/16)*(34-2*17^(1/2)-2*(34-2*17^(1/2))^(1/2)+4*(17+3*17^(1/2)-(170+38*17^(1/2))^(1/2))^(1/2))^(1/2)

I have also added compatibility with screen readers so more people can access it. I tested it with NVDA and Narrator on Windows and Talkback on Android.

Please let me know if you find some error.

[Dr Sardonicus]

Originally Posted by alpertron

Please let me know if you find some error.

Try factoring the polynomial x^5 - 5.

[alpertron]

The values found by the solver are correct as you can see by unsetting pretty print, and then factoring it again.

This is the output of the calculator.

R1 = 0
R2 = (15625)^(1/5)
R3 = 0
R4 = 0
S1 = (-1+5^(1/2))*(R1 + R4) + (-1-5^(1/2))*(R2 + R3)
S2 = (-1+5^(1/2))*(R2 + R3) + (-1-5^(1/2))*(R1 + R4)
T1 = (10 + 2 * 5^(1/2))^(1/2)*(R4 - R1) + (10 - 2 * 5^(1/2))^(1/2)*(R3 - R2)
T2 = (10 + 2 * 5^(1/2))^(1/2)*(R3 - R2) + (10 - 2 * 5^(1/2))^(1/2)*(R4 - R1)
x1 = (R1 + R2 + R3 + R4) / 5
x2 = (S1 + i * T1) / 20
x3 = (S1 - i * T1) / 20
x4 = (S2 + i * T2) / 20
x5 = (S2 - i * T2) / 20

Using Pari, we get:

%1 = I
(23:47) gp > R1 = 0
%2 = 0
(23:47) gp > R2 = (15625)^(1/5)
%3 = 6.8986483073060741619503173210800884643
(23:47) gp > R3 = 0
%4 = 0
(23:47) gp > R4 = 0
%5 = 0
(23:47) gp > S1 = (-1+5^(1/2))*(R1 + R4) + (-1-5^(1/2))*(R2 + R3)
%6 = -22.324494875306315076216696369277540320
(23:47) gp > S2 = (-1+5^(1/2))*(R2 + R3) + (-1-5^(1/2))*(R1 + R4)
%7 = 8.5271982606941667523160617271173633913
<^(1/2))^(1/2)*(R4 - R1) + (10 - 2 * 5^(1/2))^(1/2)*(R3 - R2)
%8 = -16.219694943147773999539440789223925778
<^(1/2))^(1/2)*(R3 - R2) + (10 - 2 * 5^(1/2))^(1/2)*(R4 - R1)
%9 = -26.244017705167891715114016211195788877
(23:47) gp > x1 = (R1 + R2 + R3 + R4) / 5
%10 = 1.3797296614612148323900634642160176929
(23:47) gp > x2 = (S1 + i * T1) / 20
%11 = -1.1162247437653157538108348184638770160 - 0.81098474715738869997697203946119628889*I
(23:47) gp > x3 = (S1 - i * T1) / 20
%12 = -1.1162247437653157538108348184638770160 + 0.81098474715738869997697203946119628889*I
(23:47) gp > x4 = (S2 + i * T2) / 20
%13 = 0.42635991303470833761580308635586816957 - 1.3122008852583945857557008105597894439*I
(23:47) gp > x5 = (S2 - i * T2) / 20
%14 = 0.42635991303470833761580308635586816957 + 1.3122008852583945857557008105597894439*I
(23:47) gp > f(x)=x^5-5
%15 = (x)->x^5-5
(23:48) gp > f(%11)
%16 = -2.350988701644575016 E-38 + 4.701977403289150032 E-38*I
(23:48) gp > f(%12)
%17 = -2.350988701644575016 E-38 - 4.701977403289150032 E-38*I
(23:48) gp > f(%13)
%18 = 2.350988701644575016 E-38 - 2.938735877055718770 E-38*I
(23:48) gp > f(%14)
%19 = 2.350988701644575016 E-38 + 2.938735877055718770 E-38*I
(23:48) gp > f(%10)
%20 = 4.701977403289150032 E-38

It is clear the some optimization is required in the program to delete the extra zeros so the output is reduced.

[alpertron]

Now the response of the Web application is shorter for polynomials of the form x⁵+n (n = integer).

[Dr Sardonicus]

Originally Posted by alpertron

The values found by the solver are correct as you can see by unsetting pretty print, and then factoring it again.
<snip>
It is clear the some optimization is required in the program to delete the extra zeros so the output is reduced.

My mistake, I was merely having trouble reading the output. New version with sine/cosine renderings of roots of unity is much easier on my dim old eyes, thanks!

[jwaltos]

Originally Posted by alpertron

Now the response of the Web application is shorter for polynomials of the form x⁵+n (n = integer).

Just a quick note of appreciation for your excellent work! Before I discovered this forum and links to top flight factoring software here, other than what I had rolled on my own, I was using your site (pre-2010) to factor some numbers hundreds of digits long and was able to ftp the java program and use it without logging onto the internet. I was using a 1996 laptop running Win98(special) @ .3Ghz with 10GB storage worth about $5k at the time and was able to crack some prime factors of 42 to 56 digits which I believe were records at the time but didn't report them. Many advances/changes have been made since a decade ago and your site is as good as ever. In the future I hope to provide some insights that I have made (after being suitably vetted) that may enhance some of your programs in order to tangibly reciprocate my appreciation for using your work.
Cheers.

[R. Gerbicz]

Originally Posted by alpertron

I have added more features to this calculator at https://www.alpertron.com.ar/POLFACT.HTM

Now it quickly factors integer polynomials with degree up to 1000 using Van Hoeij algorithm (which includes LLL), but notice that with some big polynomials it is possible to get an out of memory bounds so the factorization cannot complete.

..

Please let me know if you find some error.

There is a bug even in the polynom evaluation part, try for: x*(x+1)-(x+1)
it shows:
Your polynomial
−1
Clearly wrong.

[alpertron]

Originally Posted by R. Gerbicz

There is a bug even in the polynom evaluation part, try for: x*(x+1)-(x+1)
it shows:
Your polynomial
−1
Clearly wrong.

I've just fixed this error. Please refresh the page so the Web page is dated 1 October 2020 and try again.