20040103, 16:04  #1 
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. 
20040103, 17:04  #2 
Sep 2003
5025_{8} 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 6milliondigit 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. 
20040104, 09:22  #3 
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.

20040104, 10:34  #4 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
2^{3}×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 LucasLehmer test.

20040104, 16:28  #5 
Sep 2002
2×331 Posts 
Quick info on Prime95
Trial factor, use factors to 2^72 (for the larger mersennes) P1 factor, can find larger factors. LucasLehmer test, will determine if prime or composite. 
20040104, 17:15  #6 
Jan 2004
5_{16} Posts 
So the real primality is proven by a LucasLehmer 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 aPRPs and aSPRPs? 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 20040104 at 17:19 
20040104, 18:14  #7 
Sep 2003
2581_{10} Posts 
M40 exponent = 20996011, by the way
LucasLehmer 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 probableprime test on a Mersenne number instead of just doing the LucasLehmer test. 
20040104, 20:55  #8 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011100_{2} 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 LucasLehmer 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 LucasLehmer test, giving an unambiguous answer ("composite" or "definitely prime") is preferred.
You asked how primality is proved when we know the factors of N1 rather than N+1. Check out Chris Caldwell's Prime Pages at:http://www.utm.edu/research/primes/prove/ 
20040105, 13:08  #9  
Jan 2004
5 Posts 
Quote:
Quote:
One more (hopefully last ) question: How long does it take to perform a LucasLehmer test? For example on the M(40)? Last fiddled with by Alien on 20040105 at 13:10 

20040105, 21:17  #10 
Sep 2002
2×331 Posts 
LucusLehmer 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). 
20040105, 21:30  #11  
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
110101000_{2} Posts 
Quote:


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