mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-02-19, 20:13   #1
ChemicalCat59
 
Feb 2017
Somewhere on Earth

2·3 Posts
Question 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
ChemicalCat59 is offline   Reply With Quote
Old 2017-02-19, 21:09   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

19×232 Posts
Default

Some good places to start are:
https://www.mersenne.org/various/math.php
http://primes.utm.edu/mersenne/
Batalov is offline   Reply With Quote
Old 2017-02-19, 23:06   #3
GP2
 
GP2's Avatar
 
Sep 2003

50358 Posts
Default

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 2p−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 p2log(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
GP2 is offline   Reply With Quote
Old 2017-02-20, 02:48   #4
kladner
 
kladner's Avatar
 
"Kieren"
Jul 2011
In My Own Galaxy!

2·3·1,693 Posts
Default

You are truly an educational marvel, GP2.
Thanks!
kladner is offline   Reply With Quote
Old 2017-02-20, 03:18   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1001000111112 Posts
Default

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


Quote:
Originally Posted by GP2 View Post
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.
a1call is online now   Reply With Quote
Old 2017-02-20, 06:38   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2A8B16 Posts
Default

A few points to add to GP2's exceptionally good post.

For a number in the form 2P-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.)
Uncwilly is offline   Reply With Quote
Old 2017-03-22, 02:24   #7
albyva
 
"Alby"
Mar 2017
Ashburn, VA

11 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
albyva is offline   Reply With Quote
Old 2017-03-22, 14:16   #8
Mark Rose
 
Mark Rose's Avatar
 
"/X\(‘-‘)/X\"
Jan 2013

1100000011112 Posts
Default

Could GP2's layman's summary be somehow merged with the The Math page?
Mark Rose is online now   Reply With Quote
Old 2017-03-22, 22:04   #9
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

10,891 Posts
Default

Quote:
Originally Posted by Mark Rose View Post
Could GP2's layman's summary be somehow merged with the The Math page?
It would be better to edit the MersenneWiki.org
Uncwilly is offline   Reply With Quote
Old 2017-03-23, 11:14   #10
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

119210 Posts
Default

Hi all,

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

Regards,
Matt
MattcAnderson is offline   Reply With Quote
Reply

Thread Tools


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

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


Mon Jan 30 07:14:01 UTC 2023 up 165 days, 4:42, 0 users, load averages: 0.81, 1.03, 1.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔