How do you prove a number is prime?

Alien · 2004-01-03, 16:04

Hi all,

I have a question.

How do you prove a number is a prime, but I mean a number with 6 000 000 digits (for example M40)? I read somewhere that if you knew the factors of N +/- 1 you could easily prove that N is prime. How do you do this? Please tell me it's kinda interesting.

GP2 · 2004-01-03, 17:04

For numbers as large as 6 million digits like M40, it's only currently possible to prove it's prime if it has some special form (like N = 2^P-1). For a random 6-million-digit number, it's impossible with current computer speeds.

Note: quite often, when a large number is proven composite (not prime), this is done without actually finding any factor.

Alien · 2004-01-04, 09:22

OK, that's what I ask. How do you prove that a Mersenne number (in the form N = 2 ^ P - 1) is a prime? I mean you can't just do trial factoring up to sqrt(N) right? I guess that first you try trial factoring up to, let's say, 20 000 000, then if there are no factors you try a Fermat theorem to see if it could be a prime. OK up to here good. But after that what do you do? And is that the way the GIMPS's program work? And again what is that with you knowing the factors of N - 1, then you can say if N is prime.

patrik · 2004-01-04, 10:34

See http://www.mersenne.org/math.htm for how Prime95 works, and http://www.utm.edu/research/primes/n...casLehmer.html for a proof of the Lucas-Lehmer test.

dsouza123 · 2004-01-04, 16:28

Quick info on Prime95

Trial factor, use factors to 2^72 (for the larger mersennes)
P-1 factor, can find larger factors.
Lucas-Lehmer test, will determine if prime or composite.

Alien · 2004-01-04, 17:15

So the real primality is proven by a Lucas-Lehmer test (and that only, right? There are no other ways?). But this is funny. I mean S(20996009) is a ridiculously large number. How do they do this? I just can't imagine it.

So Prime95 doesn't check if a specific Mersenne number is a probable prime by a-PRPs and a-SPRPs? That's strange - I think it could save some time. But maybe I'm wrong.

P.S. Oh now I see

S0 = 4
S1 = (4 * 4 - 2) mod 127 = 14
S2 = (14 * 14 - 2) mod 127 = 67
S3 = (67 * 67 - 2) mod 127 = 42
S4 = (42 * 42 - 2) mod 127 = 111
S5 = (111 * 111 - 2) mod 127 = 0

This is how they do it. They don't calculate the whole S(20996009). That makes sense.

GP2 · 2004-01-04, 18:14

M40 exponent = 20996011, by the way

Lucas-Lehmer tests are very fast, but only work for numbers of the special form 2^P-1. For other numbers of other special forms, there are other kinds of tests. For ordinary random numbers of no special form, it's much more difficult or currently impossible when the number is very large.

There's no time gained by doing a preliminary probable-prime test on a Mersenne number instead of just doing the Lucas-Lehmer test.

philmoore · 2004-01-04, 20:55

To add to GP2's last comment: it would take virtually the same amount of time to do a probable prime test as to do a Lucas-Lehmer test. Since the result of a probable prime test may be ambiguous (i.e., probably prime doesn't necessarily mean the number is actually prime), the Lucas-Lehmer test, giving an unambiguous answer ("composite" or "definitely prime") is preferred.

You asked how primality is proved when we know the factors of N-1 rather than N+1. Check out Chris Caldwell's Prime Pages at:http://www.utm.edu/research/primes/prove/

Alien · 2004-01-05, 13:08

Quote:

Originally posted by GP2 M40 exponent = 20996011, by the way

Yes, but the Lucas-Lehmer test requires P - 2 right? So to test if 2 ^ 20996011 - 1 is prime you have to test it with S(P - 2), right? (BTW how do you do the exponent thing, I mean when the exponent is above the number in the way it is written?[sig] or something like that it was)

Quote:

Originally posted by GP2 There's no time gained by doing a preliminary probable-prime test on a Mersenne number instead of just doing the Lucas-Lehmer test.

Of course, I didn't think about it that a sort of a preliminary test is already done by choosing a prime exponent. My mistake :)

One more (hopefully last

) question: How long does it take to perform a Lucas-Lehmer test? For example on the M(40)?

dsouza123 · 2004-01-05, 21:17

Lucus-Lehmer does p - 2 iterations, the mod 2^p - 1 would be used except Prime95 uses a special FFT (dwt) which effectively does it for free.

In your example 2^7 - 1 = 127 there are 5 iterations (7 - 2 ) of
s^2 - 2 mod (2^p - 1).

patrik · 2004-01-05, 21:30

Quote:

Originally posted by Alien
One more (hopefully last ) question: How long does it take to perform a Lucas-Lehmer test? For example on the M(40)?

I ran a double check on M40 just for fun, and it took me ten days and a few hours on my 3.14 GHz P4.

2004-01-03, 16:04	#1
Alien Jan 2004 5₈ Posts	How do you prove a number is prime? Hi all, I have a question. How do you prove a number is a prime, but I mean a number with 6 000 000 digits (for example M40)? I read somewhere that if you knew the factors of N +/- 1 you could easily prove that N is prime. How do you do this? Please tell me it's kinda interesting.

2004-01-04, 17:15	#6
Alien Jan 2004 5₁₀ Posts	So the real primality is proven by a Lucas-Lehmer test (and that only, right? There are no other ways?). But this is funny. I mean S(20996009) is a ridiculously large number. How do they do this? I just can't imagine it. So Prime95 doesn't check if a specific Mersenne number is a probable prime by a-PRPs and a-SPRPs? That's strange - I think it could save some time. But maybe I'm wrong. P.S. Oh now I see S0 = 4 S1 = (4 * 4 - 2) mod 127 = 14 S2 = (14 * 14 - 2) mod 127 = 67 S3 = (67 * 67 - 2) mod 127 = 42 S4 = (42 * 42 - 2) mod 127 = 111 S5 = (111 * 111 - 2) mod 127 = 0 This is how they do it. They don't calculate the whole S(20996009). That makes sense. Last fiddled with by Alien on 2004-01-04 at 17:19

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prove 2^n cannot be a perfect number	mathgrad	Homework Help	7	2016-03-19 01:30
I take a known prime and prove it to be a composite (..or maybe need help?)	storflyt32	storflyt32	112	2015-01-09 04:19
How can I prove this PRP prime?	siegert81	Math	2	2014-11-19 10:24
Number of distinct prime factors of a Double Mersenne number	aketilander	Operazione Doppi Mersennes	1	2012-11-09 21:16
How do I prove a 4000 digit number is prime??	VJS	Lounge	4	2005-05-09 20:56

2004-01-03, 17:04	#2
GP2 Sep 2003 3²×7×41 Posts	For numbers as large as 6 million digits like M40, it's only currently possible to prove it's prime if it has some special form (like N = 2^P-1). For a random 6-million-digit number, it's impossible with current computer speeds. Note: quite often, when a large number is proven composite (not prime), this is done without actually finding any factor.

2004-01-04, 09:22	#3
Alien Jan 2004 5 Posts	OK, that's what I ask. How do you prove that a Mersenne number (in the form N = 2 ^ P - 1) is a prime? I mean you can't just do trial factoring up to sqrt(N) right? I guess that first you try trial factoring up to, let's say, 20 000 000, then if there are no factors you try a Fermat theorem to see if it could be a prime. OK up to here good. But after that what do you do? And is that the way the GIMPS's program work? And again what is that with you knowing the factors of N - 1, then you can say if N is prime.

2004-01-04, 10:34	#4
patrik "Patrik Johansson" Aug 2002 Uppsala, Sweden 110101001₂ Posts	See http://www.mersenne.org/math.htm for how Prime95 works, and http://www.utm.edu/research/primes/n...casLehmer.html for a proof of the Lucas-Lehmer test.

2004-01-04, 16:28	#5
dsouza123 Sep 2002 1226₈ Posts	Quick info on Prime95 Trial factor, use factors to 2^72 (for the larger mersennes) P-1 factor, can find larger factors. Lucas-Lehmer test, will determine if prime or composite.

2004-01-04, 18:14	#7
GP2 Sep 2003 3²×7×41 Posts	M40 exponent = 20996011, by the way Lucas-Lehmer tests are very fast, but only work for numbers of the special form 2^P-1. For other numbers of other special forms, there are other kinds of tests. For ordinary random numbers of no special form, it's much more difficult or currently impossible when the number is very large. There's no time gained by doing a preliminary probable-prime test on a Mersenne number instead of just doing the Lucas-Lehmer test.

2004-01-04, 20:55	#8
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 10001011110₂ Posts	To add to GP2's last comment: it would take virtually the same amount of time to do a probable prime test as to do a Lucas-Lehmer test. Since the result of a probable prime test may be ambiguous (i.e., probably prime doesn't necessarily mean the number is actually prime), the Lucas-Lehmer test, giving an unambiguous answer ("composite" or "definitely prime") is preferred. You asked how primality is proved when we know the factors of N-1 rather than N+1. Check out Chris Caldwell's Prime Pages at:http://www.utm.edu/research/primes/prove/

2004-01-05, 21:17	#10
dsouza123 Sep 2002 2×331 Posts	Lucus-Lehmer does p - 2 iterations, the mod 2^p - 1 would be used except Prime95 uses a special FFT (dwt) which effectively does it for free. In your example 2^7 - 1 = 127 there are 5 iterations (7 - 2 ) of s^2 - 2 mod (2^p - 1).