Calculator that can factor and find exact roots of polynomials - Page 3

R. Gerbicz · 2020-10-01, 20:46

Thanks. More examples:
polynom: x^5 - 1615*x^4 + 861790*x^3 - 174419170*x^2 + 14998420705*x - 465948627343

Irreducible polynomial factors
The 4 factors are:
x − 653
(x − 103)2
x2 − 756⁢x + 67259
Roots
The 5 roots are:
x1 = 653
x2 = x3 = 103
x4 = 103
x5 = 653

What is wrong x2-756+67259 is reducible. The correct answer should be as the roots are displayed:
(x-653)^2*(x-103)^3 . But you haven't grouped even correctly the roots in that section.

For evaluation part:

polynom: (x+1)/x*(x+1)
Your polynomial
x + 1

This is wrong.

polynom: x/2*2
your answer: Polynomial division is not integer

This could be still ok, if you require that all subresults should be in Z[x].

alpertron · 2020-10-02, 01:18

Quote:

Originally Posted by R. Gerbicz

Thanks. More examples:
polynom: x^5 - 1615*x^4 + 861790*x^3 - 174419170*x^2 + 14998420705*x - 465948627343

Irreducible polynomial factors
The 4 factors are:
x − 653
(x − 103)2
x2 − 756⁢x + 67259
Roots
The 5 roots are:
x1 = 653
x2 = x3 = 103
x4 = 103
x5 = 653

What is wrong x2-756+67259 is reducible. The correct answer should be as the roots are displayed:
(x-653)^2*(x-103)^3 . But you haven't grouped even correctly the roots in that section.

I fixed this error. Please refresh the page and retry.

Quote:

For evaluation part:

polynom: (x+1)/x*(x+1)
Your polynomial
x + 1

This is wrong.

Since the application works with integer polynomials, the slash operator performs the division disregarding the remainder.

This means that when you enter (x+1)/x*(x+1), parsing left to right, the program calculates (x+1)/x = 1 (the remainder 1 of the polynomial division is discarded) and then the program multiplies the previous result 1 by x+1, so the result is x+1.

Quote:

polynom: x/2*2
your answer: Polynomial division is not integer

This could be still ok, if you require that all subresults should be in Z[x].

Again, the expression is parsed from left to right, and x/2 is not an integer polynomial, so it shows the error.

R. Gerbicz · 2020-10-02, 16:23

OK, more inputs:

(3*x^2)/(2*x+1)
Your polynomial
3x2

Clearly wrong. Following your way it would mean that 3*x^2=(2*x+1)*3*x^2+R(x) and in this case the remainder would be 3rd degree? Meaningless.

x^5 - 4161938199135571*x^4 + 6750425908270471236962285227630*x^3 - 5309242550166291213723686988859597734543042314*x^2 + 2016699400841707878060752590276325131391118358776183137438993*x - 295975920745818133920126480489914719398004640082403818556796416884133107491

Irreducible polynomial factors
The polynomial is irreducible

Roots
The 5 roots are:
The quintic equation cannot be expressed with radicands.

Wrong, because p(x)=(x-505340926559057)^2*(x-1050418782005819)^3

Other such polynoms where you find the roots but display the wrong factors and grouping problems:
x^5 - 569676319*x^4 + 105098371422759466*x^3 - 7011576352652045449773950*x^2 + 195375348220798308339573946630661*x - 1952243687462206905824707435700917386803

and

x^5 - 2876590967309*x^4 + 3229067054667107663190970*x^3 - 1768676572192568691887072530348224746*x^2 + 473795689206607977454622626698064450356613773013*x - 49793205560537089066888851381785438595315265096906181547929

alpertron · 2020-10-02, 19:42

All these examples are working now. Thanks for finding the errors.

Please refresh the page to get the current version.

alpertron · 2020-10-04, 21:20

When the irreducible polynomial has degree >= 5, now my code performs the factorization of this polynomials with prime modulus up to 100.

If the conditions of Keith Conrad's paper that you can read at https://kconrad.math.uconn.edu/blurb...galoisSnAn.pdf are true, the Galois group is A_n or S_n, so my application indicates that the roots of the polynomial cannot be expressed as radical expressions along with the conditions found.

Example of new output from https://www.alpertron.com.ar/POLFACT.HTM

Your polynomial
x¹² + 45⁢x⁷ − 23

Irreducible polynomial factors
The polynomial is irreducible

Roots
The 12 roots are:
x1 to x12 : The roots of the polynomial cannot be expressed by radicals. The degrees of the factors of polynomial modulo 7 are 1, 2 and 9 (the Galois group contains a cycle of length 2) and the degrees of the factors of polynomial modulo 17 are 1 and 11 (the Galois group contains a cycle of prime length greater than half the degree of polynomial)

alpertron · 2020-11-28, 23:13

I fixed the LLL routine and optimized the Hensel Lifting. Now the factorization of polynomials of degree less than 1000 with small coefficients can be done in seconds.

firejuggler · 2020-11-29, 00:21

hmm

Code:

Your polynomial

x6 − 3⁢x5 − 9⁢x4 − 27⁢x3
Irreducible polynomial factors

The 4 factors are:x3
x3 − 3⁢x2 − 9⁢x − 27
Roots

The 6 roots are:x1 to x3 = 0
r = (19 + 3* sqrt(33))^1/3
s = (19 + 3* sqrt(33))^1/3
x4 = 1 + r + s
x5 = 1 − (r + s)2 + i *(( r − s)/2)* sqrt(3)
x6 = 1 − (r + s)2 + i *(( r − s)/2)* sqrt(3)

r=s and x₅=x₆
(yeah I don't know my latex)

I don't think it is a problem but... optimisation, optimisation.

R. Gerbicz · 2020-11-29, 00:33

Quote:

Originally Posted by alpertron

I fixed the LLL routine and optimized the Hensel Lifting. Now the factorization of polynomials of degree less than 1000 with small coefficients can be done in seconds.

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."

Dr Sardonicus · 2020-11-29, 15:23

Quote:

Originally Posted by firejuggler

hmm

Code:

Your polynomial

x6 − 3⁢x5 − 9⁢x4 − 27⁢x3
<snip>
The 6 roots are:x1 to x3 = 0
r = (19 + 3* sqrt(33))^1/3
s = (19 + 3* sqrt(33))^1/3
<snip>

r=s and x₅=x₆
(yeah I don't know my latex)

I don't think it is a problem but... optimisation, optimisation.

I can see one obvious problem. In the expressions for r and s, the signs of the square root should be opposite. Checking, the real value

$1\;+\;\sqrt[3]{19\;+\;3\sqrt{33}}\;+\;\sqrt[3]{19\;-\;3\sqrt{33}}$

does indeed match one of the values returned by polroots(x^3 - 3*x^3 - 9*x - 27).

alpertron · 2020-11-30, 15:47

Quote:

Originally Posted by firejuggler

hmm

Code:

Your polynomial

x6 − 3⁢x5 − 9⁢x4 − 27⁢x3
Irreducible polynomial factors

The 4 factors are:x3
x3 − 3⁢x2 − 9⁢x − 27
Roots

The 6 roots are:x1 to x3 = 0
r = (19 + 3* sqrt(33))^1/3
s = (19 + 3* sqrt(33))^1/3
x4 = 1 + r + s
x5 = 1 − (r + s)2 + i *(( r − s)/2)* sqrt(3)
x6 = 1 − (r + s)2 + i *(( r − s)/2)* sqrt(3)

r=s and x₅=x₆
(yeah I don't know my latex)

I don't think it is a problem but... optimisation, optimisation.

There is a copy error. Using your input I get:

Code:

x1 to x3 = 0
r = (19 + 3 * 33^(1/2))^(1/3)
s = (19 - 3 * 33^(1/2))^(1/3)
x4 = 1 + r + s
x5 = 1 - (r + s) / 2 + (i/2) * (r - s) * 3^(1/2)
x6 = 1 - (r + s) / 2 - (i/2) * (r - s) * 3^(1/2)

I unchecked the "Pretty Print" checkbox so it is easier to copy expressions. The signs of r and s appear to be correct.

With respect to the other error, there is a hang inside the LLL algorithm that I'm investigating.

firejuggler · 2020-11-30, 16:46

yes my bad.I shouldn't post after 1 am.

2020-10-01, 20:46	#23
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 2²·3·7·17 Posts	Thanks. More examples: polynom: x^5 - 1615x^4 + 861790x^3 - 174419170x^2 + 14998420705x - 465948627343 Irreducible polynomial factors The 4 factors are: x − 653 (x − 103)2 x2 − 756⁢x + 67259 Roots The 5 roots are: x1 = 653 x2 = x3 = 103 x4 = 103 x5 = 653 What is wrong x2-756+67259 is reducible. The correct answer should be as the roots are displayed: (x-653)^2(x-103)^3 . But you haven't grouped even correctly the roots in that section. For evaluation part: polynom: (x+1)/x(x+1) Your polynomial x + 1 This is wrong. polynom: x/22 your answer: Polynomial division is not integer This could be still ok, if you require that all subresults should be in Z[x]. Last fiddled with by R. Gerbicz on 2020-10-01 at 20:47*

2020-10-04, 21:20	#27
alpertron Aug 2002 Buenos Aires, Argentina 3²·149 Posts	When the irreducible polynomial has degree >= 5, now my code performs the factorization of this polynomials with prime modulus up to 100. If the conditions of Keith Conrad's paper that you can read at https://kconrad.math.uconn.edu/blurb...galoisSnAn.pdf are true, the Galois group is A_n or S_n, so my application indicates that the roots of the polynomial cannot be expressed as radical expressions along with the conditions found. Example of new output from https://www.alpertron.com.ar/POLFACT.HTM Your polynomial x¹² + 45⁢x⁷ − 23 Irreducible polynomial factors The polynomial is irreducible Roots The 12 roots are: x1 to x12 : The roots of the polynomial cannot be expressed by radicals. The degrees of the factors of polynomial modulo 7 are 1, 2 and 9 (the Galois group contains a cycle of length 2) and the degrees of the factors of polynomial modulo 17 are 1 and 11 (the Galois group contains a cycle of prime length greater than half the degree of polynomial) Last fiddled with by alpertron on 2020-10-04 at 21:35

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

2020-10-02, 16:23	#25
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 2²·3·7·17 Posts	OK, more inputs: (3x^2)/(2x+1) Your polynomial 3x2 Clearly wrong. Following your way it would mean that 3x^2=(2x+1)3x^2+R(x) and in this case the remainder would be 3rd degree? Meaningless. x^5 - 4161938199135571x^4 + 6750425908270471236962285227630x^3 - 5309242550166291213723686988859597734543042314x^2 + 2016699400841707878060752590276325131391118358776183137438993x - 295975920745818133920126480489914719398004640082403818556796416884133107491 Irreducible polynomial factors The polynomial is irreducible Roots The 5 roots are: The quintic equation cannot be expressed with radicands. Wrong, because p(x)=(x-505340926559057)^2(x-1050418782005819)^3 Other such polynoms where you find the roots but display the wrong factors and grouping problems: x^5 - 569676319x^4 + 105098371422759466x^3 - 7011576352652045449773950x^2 + 195375348220798308339573946630661x - 1952243687462206905824707435700917386803 and x^5 - 2876590967309x^4 + 3229067054667107663190970x^3 - 1768676572192568691887072530348224746x^2 + 473795689206607977454622626698064450356613773013*x - 49793205560537089066888851381785438595315265096906181547929

2020-10-02, 19:42	#26
alpertron Aug 2002 Buenos Aires, Argentina 3²×149 Posts	All these examples are working now. Thanks for finding the errors. Please refresh the page to get the current version.

2020-11-28, 23:13	#28
alpertron Aug 2002 Buenos Aires, Argentina 3²×149 Posts	I fixed the LLL routine and optimized the Hensel Lifting. Now the factorization of polynomials of degree less than 1000 with small coefficients can be done in seconds.

2020-11-30, 16:46	#33
firejuggler Apr 2010 Over the rainbow 100111010011₂ Posts	yes my bad.I shouldn't post after 1 am.