mersenneforum.org  

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

Reply
 
Thread Tools
Old 2008-11-24, 10:40   #1
kayjongsma
 
Sep 2008

7 Posts
Default 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.
kayjongsma is offline   Reply With Quote
Old 2008-11-24, 10:50   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,879 Posts
Default

Quote:
Originally Posted by kayjongsma View Post
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
retina is online now   Reply With Quote
Old 2008-11-24, 11:17   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

237228 Posts
Default

Quote:
Originally Posted by retina View Post
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
xilman is offline   Reply With Quote
Old 2008-11-24, 13:32   #4
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2·5·23 Posts
Default

Quote:
Originally Posted by kayjongsma View Post
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.
Jens K Andersen is offline   Reply With Quote
Old 2008-11-29, 20:27   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134628 Posts
Default

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 View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Euclid, the game VBCurtis Puzzles 0 2015-03-09 04:28
Euclid Mullin henryzz Factoring 1 2013-12-27 01:37
second Euclid-Mullin sequence arbooker Factoring 52 2013-12-03 23:00
Euclid's proof of the infinite number of primes troels munkner Miscellaneous Math 43 2010-09-06 01:36
Euclid sequences 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

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.