 mersenneforum.org Calculator that can factor and find exact roots of polynomials
 Register FAQ Search Today's Posts Mark Forums Read  2020-10-01, 20:46 #23 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 2·32·83 Posts 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]. Last fiddled with by R. Gerbicz on 2020-10-01 at 20:47   2020-10-02, 01:18   #24
alpertron

Aug 2002
Buenos Aires, Argentina

2×691 Posts 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.

Last fiddled with by alpertron on 2020-10-02 at 01:20   2020-10-02, 16:23 #25 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 2×32×83 Posts 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   2020-10-02, 19:42 #26 alpertron   Aug 2002 Buenos Aires, Argentina 138210 Posts All these examples are working now. Thanks for finding the errors. Please refresh the page to get the current version.   2020-10-04, 21:20 #27 alpertron   Aug 2002 Buenos Aires, Argentina 2·691 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 An or Sn, 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 x12 + 45⁢x7 − 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   2020-11-28, 23:13 #28 alpertron   Aug 2002 Buenos Aires, Argentina 2×691 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-29, 00:21 #29 firejuggler   Apr 2010 Over the rainbow 32×5×59 Posts 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 x5=x6 (yeah I don't know my latex) I don't think it is a problem but... optimisation, optimisation. Last fiddled with by firejuggler on 2020-11-29 at 00:22   2020-11-29, 00:33   #30
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101110101102 Posts 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."   2020-11-29, 15:23   #31
Dr Sardonicus

Feb 2017
Nowhere

22·32·139 Posts Quote:
 Originally Posted by firejuggler hmm Code: Your polynomial x6 − 3⁢x5 − 9⁢x4 − 27⁢x3 The 6 roots are:x1 to x3 = 0 r = (19 + 3* sqrt(33))1/3 s = (19 + 3* sqrt(33))1/3  r=s and x5=x6 (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

does indeed match one of the values returned by polroots(x^3 - 3*x^3 - 9*x - 27).   2020-11-30, 15:47   #32
alpertron

Aug 2002
Buenos Aires, Argentina

2·691 Posts 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 x5=x6 (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.   2020-11-30, 16:46 #33 firejuggler   Apr 2010 Over the rainbow 32·5·59 Posts yes my bad.I shouldn't post after 1 am.   Thread Tools Show Printable Version Email this Page 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 05:46.

Mon Oct 25 05:46:41 UTC 2021 up 94 days, 15 mins, 0 users, load averages: 1.07, 1.10, 1.03