20170219, 20:13  #1 
Feb 2017
Somewhere on Earth
2·3 Posts 
How do firsttime and doublecheck primality tests work?
Hello,
I am new to this project and am really interested in it. I was wondering how the tests that Prime95 runs work. If a firsttime check says it will take 30 days, but a factor is discovered 7 days in, will it stop progress and begin on a new Mersenne number? Or does it take the full 30 days for the computer's algorithm to determine the primality of the number? If someone could explain all of the different types of tests and what they mean, that would be excellent. I am fascinated by this search and curious to learn more. Thanks! Sincerely, John 
20170219, 21:09  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
19×23^{2} Posts 
Some good places to start are:
https://www.mersenne.org/various/math.php http://primes.utm.edu/mersenne/ 
20170219, 23:06  #3 
Sep 2003
5035_{8} Posts 
For each number, the first thing we do is try to find a factor. If a number has a factor, it obviously isn't prime.
The first step is trial factoring (TF). This does a thorough search for all possible factors smaller than a certain size. The exact size limit varies, but if you increase the size then the time required to do the TF testing increases very rapidly. So TF can only get you so far, but it will weed out a considerable number of candidates. For the remaining numbers where TF didn't find a factor, the next step is to continue looking for factors using socalled P−1 ("p minus one") testing. There is a specific property of Mersenne numbers which makes P−1 testing extra efficient at looking for factors of them, which is why we use P−1 testing rather than some of the other mathematical tests available. However, P−1 testing can only find a specific type of factor (indirectly associated with a property called "smoothness"). So it can't do a thorough search for all factors smaller than a certain size. However, when it does find factors, it's capable of finding factors a lot larger than the ones TF can search for. Nevertheless, just like with TF testing, there is a practical limit to the size of the factors you can find with P−1 testing. If you try to increase that limit, the time required goes up, and it also uses up more of your computer's memory. So at some point if you still haven't found any factor yet, it's time to give up on that approach and try something different. This new approach is the LucasLehmer test (LL test). It can prove with 100% certainty whether a number is prime or not prime, but it only works with numbers of a specific form: socalled Mersenne numbers, which have the form 2^{p}−1. Interestingly, when it proves that a Mersenne number is not prime, it does so without actually finding a factor. The end result of the LL test is a "residue". The Mersenne number is prime if and only if this residue is exactly zero. If the residue is not zero, we keep only the last small part of it and record this in the database. This is a 64bit hexadecimal number, consisting of the digits 0 through 9 and also the extra digits A through F, and it's exactly 16 digits long. The math required to understand exactly how the LL test actually proves anything is beyond me, and beyond most of the participants in the project. However, the actual mathematical calculations performed by the LL test are extremely simple and the LL test is exceptionally efficient, which is why nearly all attempts at finding recordsetting prime numbers focus on Mersenne numbers, and the largest known primes are nearly always of this form. We primarily use a specific finelytuned software program that squeezes out the maximum efficiency for LL testing on standard computers. The exact time required to complete the LL test varies, by the way, it's not always 30 days. The larger the exponent "p" of a Mersenne number, the more time it takes. The time goes up fairly rapidly as "p" increases, in mathematical terms it's proportional to p^{2}log(p). It's unlikely that a factor will be found while you're in the middle of doing an LL test, because by the time your computer has been assigned an LL test, it's very likely that other people have already performed an "appropriate" amount of TF testing and P−1 testing. These assignments are all coordinated by the server and the people managing the project. I mentioned "an appropriate amount", since it's unwise to overdo the TF and P−1 testing if doing so would use up more time than simply doing the LL test. The LL test will always give you an answer (prime or not prime) in an exactly predictable amount of time, whereas TF and P−1 testing are hitormiss: they might prove a number is not prime by finding a factor, but if they fail to find a factor that doesn't prove anything. So only an LL test can actually find prime numbers, and the TF and P−1 testing are just used as shortcuts to weed out and eliminate some of the numbers that would otherwise require a fullblown LL test. One final point: the very efficient LL testing program that we use is very demanding, it really puts your computer through its paces. It performs a very very large number of calculations for an extended period of time and the slightest error anywhere in the middle of those calculations will make the entire result completely worthless. In practice we find that some computers are more reliable than others: some computers used cheaper parts, and some people tinker with their computers and "overclock" them to make them run faster than the manufacturer recommends, which often comes at the expense of reliability. Therefore we make sure that LL testing for each number is performed twice, by different people. The second test serves as a double check. In practice we find that the error rate for LL testing is as high as a few percent. When the two tests come up with different residues, a triple check is needed. In rare cases, we've needed to perform up to five or more tests on the same number when all of the preceding tests give contradictory results. PS, there is one final type of testing, which is searching for factors using ECM testing. It's capable of finding factors that neither TF testing or P−1 testing can find, however this method is less efficient than simply doing an LL test, so it is only used when people try (just for fun) to find a factor for a number that was already proven to be nonprime using LL testing. ECM testing is a little like throwing darts randomly at a dartboard: if you throw a lot of darts, you might eventually hit a bulleye as long as the dartboard isn't too far away. Last fiddled with by GP2 on 20170219 at 23:12 
20170220, 02:48  #4 
"Kieren"
Jul 2011
In My Own Galaxy!
2·3·1,693 Posts 
You are truly an educational marvel, GP2.
Thanks! 
20170220, 03:18  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
100100011111_{2} Posts 
I strongly suggest this thread is turned into a sticky thread.
Thank you GP2. Coming from someone like yourself, It is very eye opening about the test and very disappointing for someone like myself to ever grasp the mechanics of the LL test. 
20170220, 06:38  #6 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2A8B_{16} Posts 
A few points to add to GP2's exceptionally good post.
For a number in the form 2^{P}1 to be prime, the P has to be prime. So that gets rid of a huge number of possible candidates from the start. Trial factoring (TF) has some interesting properties (with regards to Mersenne numbers) that allow us to know what the probability is of finding a factor at any given step (bit level). This is used to figure out if it is worth while (in the long term of the project) to keep going or to stop TF and move on. [If there is only a 5% chance of finding a factor at a given level, but it would take 25% as long to do the TF as to do the LL test, it would no make sense to do that TF. (These number are for illustration only.)] GPU are so very good for doing TF, that recently we have been doing more TF than we would have if we only used CPU's alone. So, we have found more factors (and saved the CPU's from having to do all of those LL tests.) Also, a group of people using GPU's have done all of the TF work for all of the numbers that are now being handed out (it used to be that when numbers were handed out the machine would do some final TF work, then the P1, before starting the LL test.) With P1 we can figure again what the likelihood of finding a factor is with various program settings. (The more memory available at one stage can increase the chances.) So, again we play the odds on how likely it is to find a factor vs. time to test. Here again we have some people with machines with lots of RAM, doing the P1 work Most, if not all of the numbers being handed out for first time LL testing have had a good amount of P1 work done on them (and are "ready" for LL). While 30 days is not a set length of time... over the life of the project (since about 1995), it has been about 30 days for a user with an average recent machine to complete a test in the current range. Now, with multicore machines, if the cores are working together, that can be shorter. If each core works on a different number, it will be about 2030 days to run the test (but there will be 2/4/8/etc. numbers being tested in parallel.) 
20170322, 02:24  #7  
"Alby"
Mar 2017
Ashburn, VA
11 Posts 
Quote:
Best write up I've seen anywhere. This needs to be enshrined in stone and post on the website with it's own link. When you're a n00b and see all these TF, DD, P1, LL, etc your eyeballs explode. It's good to get a plain english explanation of it all. 

20170322, 22:04  #9  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
10,891 Posts 
Quote:


20170323, 11:14  #10 
"Matthew Anderson"
Dec 2010
Oregon, USA
1192_{10} Posts 
Hi all,
Welcome to MersenneForum, Chemical Cat. I wish you many happy hours of computer calculations. Regards, Matt 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
DoubleCheck  wombatman  Conjectures 'R Us  3  20160829 20:46 
nonMersenne primality tests  Visar  Information & Answers  33  20151201 18:27 
Fastest Primality Tests  flouran  Miscellaneous Math  174  20100715 00:02 
First check and double check llrnet servers.  opyrt  Prime Sierpinski Project  3  20090102 01:50 
Doublecheck check?  M0CZY  Software  15  20081030 14:20 