mersenneforum.org The nature of the "double check"
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-03-07, 04:24 #1 Tone Float   Mar 2016 12 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-07, 10:09 #2 Nick     Dec 2012 The Netherlands 24×101 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 5×17×109 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, 10:39   #4
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts

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

Last fiddled with by Dubslow on 2016-03-07 at 10:40

 2016-03-07, 13:43 #5 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 100100100000112 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-07, 19:46   #6
ixfd64
Bemusing Prompter

"Danny"
Dec 2002
California

22·3·197 Posts

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

Last fiddled with by ixfd64 on 2016-03-07 at 19:52

 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.
2016-03-11, 03:21   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,663 Posts

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.

 2016-03-11, 05:45 #9 LaurV Romulan Interpreter     Jun 2011 Thailand 220618 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
2016-03-11, 05:59   #10
PawnProver44

"NOT A TROLL"
Mar 2016
California

197 Posts

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.

2016-03-11, 14:29   #11
ATH
Einyen

Dec 2003
Denmark

BD716 Posts

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 2n-1 not 2p - 1:

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

 Similar Threads Thread Thread Starter Forum Replies Last Post gophne gophne 272 2018-04-24 13:16 gd_barnes Sierpinski/Riesel Base 5 0 2007-12-18 20:43 Unregistered PrimeNet 16 2006-02-28 02:00 nitai1999 Software 7 2004-08-26 18:12 ixfd64 Lounge 3 2004-05-27 00:51

All times are UTC. The time now is 07:04.

Fri Feb 26 07:04:09 UTC 2021 up 85 days, 3:15, 0 users, load averages: 2.01, 2.13, 1.92