Method of Euclid's Proof

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

[retina]

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

[xilman]

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

[Jens K Andersen]

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.

[CRGreathouse]

Finding a new prime is easy. I put

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.

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.