mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2016-03-07, 04:24   #1
Tone Float
 
Mar 2016

12 Posts
Thumbs up 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?
Tone Float is offline   Reply With Quote
Old 2016-03-07, 10:09   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

24×101 Posts
Default

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.
Nick is offline   Reply With Quote
Old 2016-03-07, 10:29   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×17×109 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2016-03-07, 10:39   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

Quote:
Originally Posted by Tone Float View Post
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
Dubslow is offline   Reply With Quote
Old 2016-03-07, 13:43   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100100100000112 Posts
Default

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
Uncwilly is offline   Reply With Quote
Old 2016-03-07, 19:46   #6
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

22·3·197 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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
ixfd64 is offline   Reply With Quote
Old 2016-03-11, 01:34   #7
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

M 1213 or 2^1213 -1 is the smallest Mersenne number not fully factored.
PawnProver44 is offline   Reply With Quote
Old 2016-03-11, 03:21   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,663 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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.
Batalov is offline   Reply With Quote
Old 2016-03-11, 05:45   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

220618 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2016-03-11, 05:59   #10
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
PawnProver44 is offline   Reply With Quote
Old 2016-03-11, 14:29   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

BD716 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
ATH is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.