20210224, 19:40  #1 
"Kyle"
Feb 2005
Somewhere near M52..
3·5·61 Posts 
Fundamental Question(s) on PRP Testing
I am trying to do some reading on PRP testing to better understand the gist of how it works and why it allows us to save a significant amount of candidates from being LL tested. I have found the Wikipedia page, "Probable prime" and the Khan Academy section on Congruence modulo somewhat helpful but I certainly still do not understand the how/why as well as I would like. What other resources are available for someone to delve further into this topic?
Disclaimer: I never took beyond ordinary differential equations in undergraduate and things like "second order, nonlinear, nonhomogenous..." are a fuzzy, distant memory. My academic skillset is elsewhere. If the how/why cannot be grasped without a semester (or more) of cursory knowledge I do not possess then please let me know Thanks! Last fiddled with by Primeinator on 20210224 at 19:45 
20210224, 20:24  #2 
Aug 2006
175B_{16} Posts 
The answer isn't at all obvious from what you'd read there, so don't get down on yourself.
The way this project had run for a long time was that we'd first run a battery of preliminary tests  sieving, P1, etc.  to narrow down the field of candidates, then subject the candidates to an expensive test (the LucasLehmer test), and then finally double check the results with a second LL test. The tests went like three waves: the preliminary ones out front working on the largest numbers, the firsttime tests right behind, and then far below that the doublechecks being performed by older, slower machines. But eventually, every candidate that was not weeded out in the preliminary stage had to be checked twice with a very long test just in case the first machine that tested it had an error in calculation. (Otherwise, a prime might be wrongly listed as "composite" because of that error. The reverse error, composites being detected as primes, isn't as harmful because they're discovered since Mersenne prime reports are always verified multiple times on independent machines.) But a poster here, R. Gerbicz, came up with an improvement to the LucasLehmer test that essentially allows it to (1) back up its progress every so often and (2) either prove that it has (whp?) made no errors since the last backup, or else go back to said backup and start over. Even better, the overhead to this new test (we call it the PRP test or the Gerbicz test) is less than 1%, compared to a double check at 100%. So switching can make the project go a lot faster. 
20210224, 20:35  #3  
"Kyle"
Feb 2005
Somewhere near M52..
1110010011_{2} Posts 
Quote:
It seems like there are different types of PRP tests? (Deep breath as I am about to display my stupidity) In this example, does one keep increasing 'r' until 2^(d*2^r) is congruent to p1 mod p OR until one of this gives a noncongruent result? Edit: Example did not copy paste appropriately. I posted "Step 4" under the "Example of SPRP" on the Wikipedia page for "Probable Prime". Last fiddled with by Primeinator on 20210224 at 20:41 

20210224, 20:36  #4 
Sep 2002
Database er0rr
3,853 Posts 
Surely you did the binomial theorem. (a+b)^n = a^n + binom(n,1)*a^(n1)*b + binom(n,2)*a^(n2)*b^2 + ... + b^n. Now think about a particular binom(n,k). It is n!/(k!*(nk)!). If n was prime then neither k! nor (nk)! have n as a factor and so binom(n,k) must be divisible by the prime since n divides n! So working mod n all the binom are 0. That is (a+b)^n = a^n + b^n. 1^n == 1 and (1+j)^n = 1 + j^n. Put j = 1 the 2^n = 1+1^n. And so on (1+2)^n = 1 + 2^n = 1 + 2 ...
I will defer to RG to show how Gerbicz error checking works with Mersenne candidates. It means the chance of an error being missed is extremely small. Thus we can have great confidence in the result and no need for 2 matching LL results to be calculated since Prime95 etc does hashes to produce a sort of certificate of testing. 
20210224, 20:49  #5  
Sep 2002
Database er0rr
3,853 Posts 
Quote:


20210224, 21:06  #6 
"Kyle"
Feb 2005
Somewhere near M52..
1110010011_{2} Posts 
Yes, though I do not remember applying it extremely extensively or time has dulled my memory. I do not recall using the nCk notation. I do somewhat recall n! / (k!(nk)!) though your point as to why if n is prime then neither k! or (nk)! have n as a factor is lost on me though clearly the answer must be obvious. I did warn you... my math knowledge has atrophied significantly and was not extremely robust to begin with.
Last fiddled with by Primeinator on 20210224 at 21:09 
20210224, 21:10  #7  
Sep 2002
Database er0rr
F0D_{16} Posts 
Quote:
Last fiddled with by paulunderwood on 20210224 at 21:13 

20210224, 22:10  #8  
"Kyle"
Feb 2005
Somewhere near M52..
3·5·61 Posts 
Quote:
Quote:
Last fiddled with by Primeinator on 20210224 at 22:23 

20210224, 22:18  #9  
Sep 2002
Database er0rr
3,853 Posts 
Quote:
Here is a concrete example 7!/(5!*2!). Here 7 divides 7! but not 5! or 2! Last fiddled with by paulunderwood on 20210224 at 22:26 

20210224, 22:32  #10 
"Kyle"
Feb 2005
Somewhere near M52..
3·5·61 Posts 

20210224, 22:52  #11  
Sep 2002
Database er0rr
3,853 Posts 
Quote:
In my example 7!/(5!*2!). Don't forget not to divide by n. We have 7*6*5*4*3*2*1 / ( 5*4*3*2*1 * 2*1 ). If n is not prime we cannot guarantee this binom = 0 mod n. For example n=8. Then 8!/(4!*4!) = 8*7*6*5 / ( 4*3*2*1 ) which has 4 factors of 2 in the numerator and 3 in the denominator. So after cancellation of terms there will be one 2 left in the numerator. So it cannot be 0 mod 8. Last fiddled with by paulunderwood on 20210224 at 22:59 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New fundamental result in PDEs  ewmayer  Math  4  20130401 02:39 
Forcing testing of F14[2^(2^14)+1] question  jasong  PrimeNet  3  20090707 22:31 
I generalized the fundamental theorem of calculus  Damian  Math  16  20071105 14:55 
Fundamental particle found with no charge.  mfgoode  Science & Technology  5  20061212 17:20 
newbie question  testing primality of very large numbers  NeoGen  Software  8  20060320 01:22 