mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-09-10, 14:18   #1
jfollas
 
Jul 2004

168 Posts
Default General Solution to Polynomial Equations

What are the implications for factoring/primality testing (if any) of the newly announced general solution to polynomial equations? This piqued my interest because I remembered something about FFT being based on representing numbers as polynomial equations (sorry if I'm incorrect).

http://arxiv.org/ftp/math/papers/0408/0408264.pdf
jfollas is offline   Reply With Quote
Old 2004-09-10, 19:15   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by jfollas
What are the implications for factoring/primality testing (if any) of the newly announced general solution to polynomial equations? This piqued my interest because I remembered something about FFT being based on representing numbers as polynomial equations (sorry if I'm incorrect).

http://arxiv.org/ftp/math/papers/0408/0408264.pdf
(1) The so-called "new" solution to polynomial equations is at least 100
years old. It is a lot of media ignorance and hype. Methods have been around
since the time of Hermite (or earlier). Since polynomials are 1-1 in the close
neighborhood of any root, you can always find an infinite series representation
to the root (by the Inverse Function Thm). This so-called "new" method is
nothing more than an infinite series solution. But it has been known for a long
time that roots could be expressed in terms of Elliptic or Hypergeometric or
Theta functions.

(2) It has ZERO implications for factoring/prime testing.

I am curious as to why you think there MIGHT be a connection?
R.D. Silverman is offline   Reply With Quote
Old 2004-09-10, 19:27   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22×7×281 Posts
Default

Apparently this is hitting the news big time...

http://science.slashdot.org/science/.../1229221.shtml
Xyzzy is offline   Reply With Quote
Old 2004-09-11, 12:51   #4
jfollas
 
Jul 2004

2×7 Posts
Default

Quote:
Originally Posted by Bob Silverman
I am curious as to why you think there MIGHT be a connection?
What stuck in my mind was that when you multiply using FFT, you first represent the number as a polynomial equation:

57829 = 5x^4 + 7x^3 + 8x^2 + 2x + 9

I wasn't sure if the roots of such an equation were useful for factoring, etc, since the article made it seem like it was one of nature's unsolved mysteries (or something) to have a general equation for numerically solving polynomial equations.
jfollas is offline   Reply With Quote
Old 2004-09-11, 14:10   #5
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

Hmm, I thought that the Newton-Rhapson method already provided a method for finding the roots of any polynomial numerically to arbitrarily high accuracy.

Last fiddled with by jinydu on 2004-09-11 at 14:12
jinydu is offline   Reply With Quote
Old 2004-09-13, 11:36   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by jfollas
What stuck in my mind was that when you multiply using FFT, you first represent the number as a polynomial equation:

57829 = 5x^4 + 7x^3 + 8x^2 + 2x + 9

I wasn't sure if the roots of such an equation were useful for factoring, etc, since the article made it seem like it was one of nature's unsolved mysteries (or something) to have a general equation for numerically solving polynomial equations.
But all numbers have an instantiation as a polynomial (in a particular base)
What makes you think that there is something special here?
R.D. Silverman is offline   Reply With Quote
Old 2004-09-13, 11:38   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by jinydu
Hmm, I thought that the Newton-Rhapson method already provided a method for finding the roots of any polynomial numerically to arbitrarily high accuracy.

Your premise is not correct.

I suggest that you apply Newton's method to (say) x^3 - 3x^2 + 4.
R.D. Silverman is offline   Reply With Quote
Old 2004-09-13, 20:49   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

289E16 Posts
Default

Quote:
Originally Posted by Bob Silverman
Your premise is not correct.

I suggest that you apply Newton's method to (say) x^3 - 3x^2 + 4.


For extra points, explain why it all goes badly wrong.

Paul
xilman is offline   Reply With Quote
Old 2004-09-14, 02:26   #9
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default

Quote:
Originally Posted by Bob Silverman
Your premise is not correct.

I suggest that you apply Newton's method to (say) x^3 - 3x^2 + 4.
Ok, here goes my attempt:

Let f(x) = x^3 - 3x^2 + 4
Then f '(x) = 3x^2 - 6x

My first guess will be x = 1
f(1) = 2
f '(1) = -3
Next guess = 1 - (2/-3) = 5/3 ~= 1.6666666666666666666

Second guess is x = 5/3
f(5/3) = 8/27
f '(5/3) = -5/3
Next guess = (5/3) - ([8/27]/[-5/3]) = 83/45 ~= 1.8444444444444444

The next two iterations give:

21563/11205 ~= 1.92440875
1422643403/724840245 ~= 1.96269925

The method seems to be working, or did I just get lucky with my starting guess?
jinydu is offline   Reply With Quote
Old 2004-09-14, 13:00   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

Quote:
Originally Posted by jinydu
Ok, here goes my attempt:

Let f(x) = x^3 - 3x^2 + 4
Then f '(x) = 3x^2 - 6x

My first guess will be x = 1
f(1) = 2
f '(1) = -3
Next guess = 1 - (2/-3) = 5/3 ~= 1.6666666666666666666

Second guess is x = 5/3
f(5/3) = 8/27
f '(5/3) = -5/3
Next guess = (5/3) - ([8/27]/[-5/3]) = 83/45 ~= 1.8444444444444444

The next two iterations give:

21563/11205 ~= 1.92440875
1422643403/724840245 ~= 1.96269925

The method seems to be working, or did I just get lucky with my starting guess?
May I suggest that you continue..... You will find that convergence
gets slower and slower and slower and.......

Ask yourself: what is special about the polynomial I gave?

I did not choose it randomly....
R.D. Silverman is offline   Reply With Quote
Old 2004-09-14, 14:27   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,733 Posts
Default

Quote:
Originally Posted by Bob Silverman
May I suggest that you continue..... You will find that convergence
gets slower and slower and slower and.......

Ask yourself: what is special about the polynomial I gave?

I did not choose it randomly....
To be fair, he did say "to arbitrarily high accuracy". He didn't say it would do so rapidly. Neither did he say that he'd use floating point arithmetic with precision so low that he'd run into rounding errors.

That's why I put a smiley after quoting your example, and why I asked him to explain why it all goes terribly wrong.

I'm well aware, of course, why you chose that particular polynomial.

Paul
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
My solution for the problem of microtransactions and media in general jasong jasong 21 2019-08-19 14:59
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
solving 2nd order differential equations Joshua2 Homework Help 9 2009-10-30 07:37
Navier-Stocks equations mfgoode Math 1 2006-10-09 16:02
Equality of quadratic equations dsouza123 Math 2 2004-07-30 09:03

All times are UTC. The time now is 09:08.

Fri Dec 4 09:08:39 UTC 2020 up 1 day, 5:19, 0 users, load averages: 1.81, 1.46, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.