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 non-primality, if you could easily cite a factor.

Or am I completely wrong about how it works?

The main test used by GIMPS is the Lucas-Lehmer algorithm, which works as follows:

Suppose p is an odd prime number and we wish to know whether \(2^p-1\) is prime. We start with the number 4 (there are other values which work too) and then repeat the following p-2 times:
square the current number then subtract 2, working modulo \(2^p-1\) (i.e. after each step, we divide by \(2^p-1\) and take the remainder).
Then \(2^p-1\) is a prime number if (and only if) we get zero at the end.

If \(2^p-1\) is not a prime number, then this test tells us that without producing a factor.

Such DB exists. Check [URL="http://www.mersenne.org/various/math.php"]this page[/URL] to understand how it works. We don't run LL tests for numbers for which we know a factor, it would make no sense, they can't be prime.

[QUOTE=Tone Float;428255]
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?
[/QUOTE]

Roughly 60-65% of Mersenne candidates are factored by GIMPS, in order to avoid the relatively expensive LL tests (and GIMPS of course records each and every one of those factors, millions of them). For the balance, there is no easily found factor, i.e. it is less computationally expensive to run the LL test (which by the way is deterministic, and whose mathematical basis as a proof of compositeness is equally solid as a factor or as 1+1=2).

See the link that LaurV posted -- it answers the exact questions you have with more details (without being overwhelming [hopefully]).

In addition to what the others said I will provide a link to an article about the L-L test.
[url]http://mersennewiki.org/index.php/Lucas-Lehmer_Test[/url]

[QUOTE=Dubslow;428284]Roughly 60-65% of Mersenne candidates are factored by GIMPS, in order to avoid the relatively expensive LL tests (and GIMPS of course records each and every one of those factors, millions of them). For the balance, there is no easily found factor, i.e. it is less computationally expensive to run the LL test (which by the way is deterministic, and whose mathematical basis as a proof of compositeness is equally solid as a factor or as 1+1=2).

See the link that LaurV posted -- it answers the exact questions you have with more details (without being overwhelming [hopefully]).[/QUOTE]

In cases where a factor is later found for an exponent with mismatching residues, an additional LL test is sometimes the only way to determine which computers are bad. I believe Aaron sometimes does this. Here is an example: [url]http://mersenne.org/M17245747[/url]

M 1213 or 2^1213 -1 is the smallest Mersenne number not fully factored.

[QUOTE=PawnProver44;428682]M 1213 or 2^1213 -1 is the smallest Mersenne number not fully factored.[/QUOTE]
False.
[URL="http://factordb.com/index.php?query=2^1207-1"]2^1207-1[/URL] is smaller and not fully factored [U]at this time[/U].

Are you trying to set a record of "[URL="http://mersenneforum.org/showpost.php?p=428679"]most[/URL] [URL="http://mersenneforum.org/showthread.php?p=428644#post428644"]wrongs[/URL] [URL="http://mersenneforum.org/showthread.php?p=428646#post428646"]per[/URL] unit of time"? It is a futile effort. Any record you can set, you can beat easily the next minute.

Technically, with the restricted definition of mersenne numbers, he is right, because 1207 is not prime :razz:

OTOH, I think he is only trolling.

[QUOTE=Batalov;428696]False.
[URL="http://factordb.com/index.php?query=2^1207-1"]2^1207-1[/URL] is smaller and not fully factored [U]at this time[/U].

Are you trying to set a record of "[URL="http://mersenneforum.org/showpost.php?p=428679"]most[/URL] [URL="http://mersenneforum.org/showthread.php?p=428644#post428644"]wrongs[/URL] [URL="http://mersenneforum.org/showthread.php?p=428646#post428646"]per[/URL] unit of time"? It is a futile effort. Any record you can set, you can beat easily the next minute.[/QUOTE]

1207 is composite, I am talking about prime exponents, see.

[QUOTE=LaurV;428706]Technically, with the restricted definition of mersenne numbers, he is right, because 1207 is not prime :razz:

OTOH, I think he is only trolling.[/QUOTE]

Actually a "Mersenne Number" is 2[SUP]n[/SUP]-1 not 2[SUP]p[/SUP] - 1:

[url]http://mathworld.wolfram.com/MersenneNumber.html[/url]