mersenneforum.org > Math How do you prove a number is prime?
 Register FAQ Search Today's Posts Mark Forums Read

 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-03, 17:04 #2 GP2     Sep 2003 2·1,291 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 = 2P-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 58 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 23×53 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 2·331 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, 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
 2004-01-04, 18:14 #7 GP2     Sep 2003 2×1,291 Posts M40 exponent = 20996011, by the way Lucas-Lehmer tests are very fast, but only work for numbers of the special form 2P-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. 2·13·43 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, 13:08   #9
Alien

Jan 2004

58 Posts

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

Last fiddled with by Alien on 2004-01-05 at 13:10

 2004-01-05, 21:17 #10 dsouza123     Sep 2002 66210 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).
2004-01-05, 21:30   #11
patrik

"Patrik Johansson"
Aug 2002
Uppsala, Sweden

23×53 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post mathgrad Homework Help 7 2016-03-19 01:30 storflyt32 storflyt32 112 2015-01-09 04:19 siegert81 Math 2 2014-11-19 10:24 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 VJS Lounge 4 2005-05-09 20:56

All times are UTC. The time now is 08:32.

Thu Dec 3 08:32:58 UTC 2020 up 4:44, 0 users, load averages: 1.23, 1.24, 1.10