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.

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[sup]P[/sup]-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.

OK, that's what I ask. How do you [U][B]prove[/B][/U] 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.

See [url]http://www.mersenne.org/math.htm[/url] for how Prime95 works, and [url]http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html[/url] for a proof of the Lucas-Lehmer test.

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.

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.

M40 exponent = 20996011, by the way

Lucas-Lehmer tests are very fast, but only work for numbers of the special form 2[sup]P[/sup]-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.

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:[URL]http://www.utm.edu/research/primes/prove/[/URL]

[QUOTE][i][B]Originally posted by GP2 [/i]M40 exponent = 20996011, by the way[/B][/QUOTE]

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][i][B]Originally posted by GP2 [/i]There's no time gained by doing a preliminary probable-prime test on a Mersenne number instead of just doing the Lucas-Lehmer test.[/B][/QUOTE]

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 :smile: ) question: How long does it take to perform a Lucas-Lehmer test? For example on the M(40)?

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

[QUOTE][i]Originally posted by Alien [/i]
[B]One more (hopefully last :smile: ) question: How long does it take to perform a Lucas-Lehmer test? For example on the M(40)? [/B][/QUOTE] 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.