The nature of the "double check"

Tone Float · 2016-03-07, 04:24

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?

Nick · 2016-03-07, 10:09

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.

LaurV · 2016-03-07, 10:29

Such DB exists. Check this page 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.

Dubslow · 2016-03-07, 10:39

Quote:

Originally Posted by Tone Float

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?

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]).

Uncwilly · 2016-03-07, 13:43

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

ixfd64 · 2016-03-07, 19:46

Quote:

Originally Posted by Dubslow

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 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: http://mersenne.org/M17245747

PawnProver44 · 2016-03-11, 01:34

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

Batalov · 2016-03-11, 03:21

Quote:

Originally Posted by PawnProver44

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

False.
2^1207-1 is smaller and not fully factored at this time.

Are you trying to set a record of "most wrongs per unit of time"? It is a futile effort. Any record you can set, you can beat easily the next minute.

LaurV · 2016-03-11, 05:45

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

OTOH, I think he is only trolling.

PawnProver44 · 2016-03-11, 05:59

Quote:

Originally Posted by Batalov

False.
2^1207-1 is smaller and not fully factored at this time.

Are you trying to set a record of "most wrongs per unit of time"? It is a futile effort. Any record you can set, you can beat easily the next minute.

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

ATH · 2016-03-11, 14:29

Quote:

Originally Posted by LaurV

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

OTOH, I think he is only trolling.

Actually a "Mersenne Number" is 2ⁿ-1 not 2^p - 1:

http://mathworld.wolfram.com/MersenneNumber.html

2016-03-07, 04:24	#1
Tone Float Mar 2016 1 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 non-primality, if you could easily cite a factor. Or am I completely wrong about how it works?

2016-03-11, 05:45	#9
LaurV Romulan Interpreter Jun 2011 Thailand 22612₈ 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 2016-03-11 at 05:46

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

2016-03-07, 10:09	#2
Nick Dec 2012 The Netherlands 2·23·37 Posts	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.

2016-03-07, 10:29	#3
LaurV Romulan Interpreter Jun 2011 Thailand 22612₈ Posts	Such DB exists. Check this page 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.

2016-03-07, 13:43	#5
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2³·1,223 Posts	In addition to what the others said I will provide a link to an article about the L-L test. http://mersennewiki.org/index.php/Lucas-Lehmer_Test

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