mersenneforum.org  

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

Reply
 
Thread Tools
Old 2004-01-03, 16:04   #1
Alien
 
Jan 2004

5 Posts
Default 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.
Alien is offline   Reply With Quote
Old 2004-01-03, 17:04   #2
GP2
 
GP2's Avatar
 
Sep 2003

50258 Posts
Default

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.
GP2 is offline   Reply With Quote
Old 2004-01-04, 09:22   #3
Alien
 
Jan 2004

5 Posts
Default

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.
Alien is offline   Reply With Quote
Old 2004-01-04, 10:34   #4
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

23×53 Posts
Default

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.
patrik is offline   Reply With Quote
Old 2004-01-04, 16:28   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2004-01-04, 17:15   #6
Alien
 
Jan 2004

516 Posts
Default

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
Alien is offline   Reply With Quote
Old 2004-01-04, 18:14   #7
GP2
 
GP2's Avatar
 
Sep 2003

258110 Posts
Default

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.
GP2 is offline   Reply With Quote
Old 2004-01-04, 20:55   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111002 Posts
Default

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/
philmoore is offline   Reply With Quote
Old 2004-01-05, 13:08   #9
Alien
 
Jan 2004

5 Posts
Default

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
Alien is offline   Reply With Quote
Old 2004-01-05, 21:17   #10
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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).
dsouza123 is offline   Reply With Quote
Old 2004-01-05, 21:30   #11
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

1101010002 Posts
Default

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.
patrik is offline   Reply With Quote
Reply

Thread Tools


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

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

Wed Oct 21 02:08:09 UTC 2020 up 40 days, 23:19, 0 users, load averages: 1.64, 1.64, 1.65

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.