How do first-time and double-check primality tests work?

ChemicalCat59 · 2017-02-19, 20:13

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 first-time 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

Batalov · 2017-02-19, 21:09

Some good places to start are:
https://www.mersenne.org/various/math.php
http://primes.utm.edu/mersenne/

GP2 · 2017-02-19, 23:06

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 so-called 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 Lucas-Lehmer 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: so-called 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 64-bit 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 record-setting prime numbers focus on Mersenne numbers, and the largest known primes are nearly always of this form. We primarily use a specific finely-tuned 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²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 hit-or-miss: 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 full-blown 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 non-prime 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.

kladner · 2017-02-20, 02:48

You are truly an educational marvel, GP2.

Thanks!

a1call · 2017-02-20, 03:18

I strongly suggest this thread is turned into a sticky thread.
Thank you GP2.

Quote:

Originally Posted by GP2

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.

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.

Uncwilly · 2017-02-20, 06:38

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 P-1, before starting the LL test.)

With P-1 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 P-1 work Most, if not all of the numbers being handed out for first time LL testing have had a good amount of P-1 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 20-30 days to run the test (but there will be 2/4/8/etc. numbers being tested in parallel.)

albyva · 2017-03-22, 02:24

Quote:

Originally Posted by GP2

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.

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, P-1, LL, etc your eyeballs explode. It's good to get a plain english explanation of it all.

Mark Rose · 2017-03-22, 14:16

Could GP2's layman's summary be somehow merged with the The Math page?

Uncwilly · 2017-03-22, 22:04

Quote:

Originally Posted by Mark Rose

Could GP2's layman's summary be somehow merged with the The Math page?

It would be better to edit the MersenneWiki.org

MattcAnderson · 2017-03-23, 11:14

Hi all,

Welcome to MersenneForum, Chemical Cat. I wish you many happy hours of computer calculations.

Regards,
Matt

2017-02-19, 20:13	#1
ChemicalCat59 Feb 2017 Somewhere on Earth 2·3 Posts	How do first-time and double-check 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 first-time 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

2017-02-19, 23:06	#3
GP2 Sep 2003 5035₈ 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 so-called 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 Lucas-Lehmer 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: so-called 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 64-bit 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 record-setting prime numbers focus on Mersenne numbers, and the largest known primes are nearly always of this form. We primarily use a specific finely-tuned 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²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 hit-or-miss: 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 full-blown 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 non-prime 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 2017-02-19 at 23:12

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Double-Check	wombatman	Conjectures 'R Us	3	2016-08-29 20:46
non-Mersenne primality tests	Visar	Information & Answers	33	2015-12-01 18:27
Fastest Primality Tests	flouran	Miscellaneous Math	174	2010-07-15 00:02
First check and double check llrnet servers.	opyrt	Prime Sierpinski Project	3	2009-01-02 01:50
Double-check check?	M0CZY	Software	15	2008-10-30 14:20

2017-02-19, 21:09	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 19×23² Posts	Some good places to start are: https://www.mersenne.org/various/math.php http://primes.utm.edu/mersenne/

2017-02-20, 02:48	#4
kladner "Kieren" Jul 2011 In My Own Galaxy! 2·3·1,693 Posts	You are truly an educational marvel, GP2. Thanks!

2017-02-20, 06:38	#6
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2A8B₁₆ 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 P-1, before starting the LL test.) With P-1 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 P-1 work Most, if not all of the numbers being handed out for first time LL testing have had a good amount of P-1 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 20-30 days to run the test (but there will be 2/4/8/etc. numbers being tested in parallel.)

2017-03-22, 14:16	#8
Mark Rose "/X\(‘-‘)/X\" Jan 2013 110000001111₂ Posts	Could GP2's layman's summary be somehow merged with the The Math page?

2017-03-23, 11:14	#10
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 1192₁₀ Posts	Hi all, Welcome to MersenneForum, Chemical Cat. I wish you many happy hours of computer calculations. Regards, Matt