20160307, 04:24  #1 
Mar 2016
1_{2} Posts 
The nature of the "double check"
My understanding is that GIMPS checks, and double checks each potential Mersenne prime. For the vast majority of cases  where the first check indicates it's not a prime, is the double check done the same way as the first run?
If so, wouldn't it be easier to create a database of primality counterexamples, that is, a known factor (not necessarily an exhaustive list of all factors) of each potential Mersenne prime, in which case the double check becomes trivially easier  just divide by the factor and show it isn't prime? Would also be easier to demonstrate to skeptics of a number's particular nonprimality, if you could easily cite a factor. Or am I completely wrong about how it works? 
20160307, 10:09  #2 
Dec 2012
The Netherlands
2^{4}×101 Posts 
The main test used by GIMPS is the LucasLehmer algorithm, which works as follows:
Suppose p is an odd prime number and we wish to know whether \(2^p1\) is prime. We start with the number 4 (there are other values which work too) and then repeat the following p2 times: square the current number then subtract 2, working modulo \(2^p1\) (i.e. after each step, we divide by \(2^p1\) and take the remainder). Then \(2^p1\) is a prime number if (and only if) we get zero at the end. If \(2^p1\) is not a prime number, then this test tells us that without producing a factor. 
20160307, 10:39  #4  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1110000110101_{2} Posts 
Quote:
See the link that LaurV posted  it answers the exact questions you have with more details (without being overwhelming [hopefully]). Last fiddled with by Dubslow on 20160307 at 10:40 

20160307, 13:43  #5 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
10010010000011_{2} Posts 
In addition to what the others said I will provide a link to an article about the LL test.
http://mersennewiki.org/index.php/LucasLehmer_Test 
20160307, 19:46  #6  
Bemusing Prompter
"Danny"
Dec 2002
California
2^{2}·3·197 Posts 
Quote:
Last fiddled with by ixfd64 on 20160307 at 19:52 

20160311, 01:34  #7 
"NOT A TROLL"
Mar 2016
California
197 Posts 
M 1213 or 2^1213 1 is the smallest Mersenne number not fully factored.

20160311, 03:21  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,663 Posts 

20160311, 05:45  #9 
Romulan Interpreter
Jun 2011
Thailand
22061_{8} Posts 
Technically, with the restricted definition of mersenne numbers, he is right, because 1207 is not prime
OTOH, I think he is only trolling. Last fiddled with by LaurV on 20160311 at 05:46 
20160311, 05:59  #10 
"NOT A TROLL"
Mar 2016
California
197 Posts 
1207 is composite, I am talking about prime exponents, see.

20160311, 14:29  #11  
Einyen
Dec 2003
Denmark
BD7_{16} Posts 
Quote:
http://mathworld.wolfram.com/MersenneNumber.html 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
"New" primality test/check  gophne  gophne  272  20180424 13:16 
"Conjecture 'R Us" effort, come check it out!  gd_barnes  Sierpinski/Riesel Base 5  0  20071218 20:43 
Speeding up double checking when first test returns "prime"  Unregistered  PrimeNet  16  20060228 02:00 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 
suggestion: "check exponent status" page  ixfd64  Lounge  3  20040527 00:51 