mersenneforum.org > Math Method of Euclid's Proof
 Register FAQ Search Today's Posts Mark Forums Read

 2008-11-24, 10:40 #1 kayjongsma   Sep 2008 7 Posts Method of Euclid's Proof I was wondering why the method of Euclid's proof isn't used to find world's largest primes... To find a new prime,you could just multiply all primes up to a certain number, and then add one. If you're sure you didn't miss a prime you've found a new one. maybe the primes found this way don't grow fast enough? I'm probably missing a simple thing.
2008-11-24, 10:50   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5,879 Posts

Quote:
 Originally Posted by kayjongsma I was wondering why the method of Euclid's proof isn't used to find world's largest primes... To find a new prime,you could just multiply all primes up to a certain number, and then add one. If you're sure you didn't miss a prime you've found a new one. maybe the primes found this way don't grow fast enough? I'm probably missing a simple thing.
Because, even though you know there is a new prime there, the problem is to identify it.

After having done all the multiplies and added 1 now how do you know if the result is a prime? You need some sort of test to determine if your number is prime. Not as easy as it might seem. And even if you determine it is not prime, how do you find the divisors? Again you need some sort of method to extract the necessary information.

It is not good enough just to say "Oh, there is a new prime in there somewhere, but I don't know what it is".

Last fiddled with by retina on 2008-11-24 at 10:51

2008-11-24, 11:17   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

237228 Posts

Quote:
 Originally Posted by retina Because, even though you know there is a new prime there, the problem is to identify it. After having done all the multiplies and added 1 now how do you know if the result is a prime? You need some sort of test to determine if your number is prime. Not as easy as it might seem. And even if you determine it is not prime, how do you find the divisors? Again you need some sort of method to extract the necessary information. It is not good enough just to say "Oh, there is a new prime in there somewhere, but I don't know what it is".
Concrete example:

2*3*5*7*11*13 + 1 = 30031
59 * 509 = 30031

Paul

2008-11-24, 13:32   #4
Jens K Andersen

Feb 2006
Denmark

2·5·23 Posts

Quote:
 Originally Posted by kayjongsma To find a new prime,you could just multiply all primes up to a certain number, and then add one. If you're sure you didn't miss a prime you've found a new one.
This is based on a common misunderstanding of Euclid's proof. As Xilman's example shows, there are actually two possiblities: The number may be prime or it may be composite with prime factors which are larger than the multiplied primes. In the vast majority of tested cases, and probably almost all cases, it is the second possibility. Then there is no known feasible method to find the large prime factors.

2008-11-29, 20:27   #5
CRGreathouse

Aug 2006

134628 Posts

Finding a new prime is easy. I put
Code:
nextprime(random(10^65))
into Pari which generated
70486640254630306486542498129083911644039810089312084380333291127
(I then verified this in about two-tenths of a second with isprime(%)), a prime that in all likelihood no one has ever seen before.

Quote:
 Originally Posted by Jens K Andersen As Xilman's example shows, there are actually two possiblities: The number may be prime or it may be composite with prime factors which are larger than the multiplied primes. In the vast majority of tested cases, and probably almost all cases, it is the second possibility. Then there is no known feasible method to find the large prime factors.
Yes, this is a really difficult method for finding primes. I was trying to factor 2 * 3 * 7 * 43 * 13 * ... + 1 to extend the Sloane sequence -- the number is large enough that it's feasible only with the elliptic curve method; the NFS would take too long.

 Similar Threads Thread Thread Starter Forum Replies Last Post VBCurtis Puzzles 0 2015-03-09 04:28 henryzz Factoring 1 2013-12-27 01:37 arbooker Factoring 52 2013-12-03 23:00 troels munkner Miscellaneous Math 43 2010-09-06 01:36 Maybeso Math 2 2003-08-08 17:55

All times are UTC. The time now is 23:38.

Wed Nov 25 23:38:18 UTC 2020 up 76 days, 20:49, 3 users, load averages: 1.08, 1.11, 1.20