mersenneforum.org Fundamental Question(s) on PRP Testing
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-02-24, 19:40 #1 Primeinator     "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, non-linear, non-homogenous..." 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 2021-02-24 at 19:45
 2021-02-24, 20:24 #2 CRGreathouse     Aug 2006 3×1,993 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, P-1, etc. -- to narrow down the field of candidates, then subject the candidates to an expensive test (the Lucas-Lehmer 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 first-time tests right behind, and then far below that the double-checks 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 Lucas-Lehmer 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.
2021-02-24, 20:35   #3
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

11100100112 Posts

Quote:
 Originally Posted by CRGreathouse The way this project had run for a long time was that we'd first run a battery of preliminary tests -- sieving, P-1, etc.
This was the state of things when I took my "leave". Sieving, the two stages of P-1, and then LL test with a DC LL test later. It's truly awesome to see the ingenuity some people possess and how much the workflow of the project has changed.

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 p-1 mod p OR until one of this gives a non-congruent 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 2021-02-24 at 20:41

 2021-02-24, 20:36 #4 paulunderwood     Sep 2002 Database er0rr 72538 Posts Surely you did the binomial theorem. (a+b)^n = a^n + binom(n,1)*a^(n-1)*b + binom(n,2)*a^(n-2)*b^2 + ... + b^n. Now think about a particular binom(n,k). It is n!/(k!*(n-k)!). If n was prime then neither k! nor (n-k)! 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.
2021-02-24, 20:49   #5
paulunderwood

Sep 2002
Database er0rr

5·751 Posts

Quote:
 Originally Posted by Primeinator This was the state of things when I took my "leave". Sieving, the two stages of P-1, and then LL test with a DC LL test later. It's truly awesome to see the ingenuity some people possess and how much the workflow of the project has changed. 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 p-1 mod p OR until one of this gives a non-congruent result? Edit: Example did not copy paste appropriately. I posted "Step 4" under the "Example of SPRP" on the Wikipedia page for "Probable Prime".
Since for prime n we have a^n== a mod n then a^(n-1) == 1. We can take a square root a^((n-1)/2) and expect the result to be +- 1. If it is 1 and we can take another square root by dividing the exponent by 2 again we expect the result to be +- 1.

2021-02-24, 21:06   #6
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts

Quote:
 Originally Posted by paulunderwood Surely you did the binomial theorem.
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!(n-k)!) though your point as to why if n is prime then neither k! or (n-k)! 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 2021-02-24 at 21:09

2021-02-24, 21:10   #7
paulunderwood

Sep 2002
Database er0rr

1110101010112 Posts

Quote:
 Originally Posted by Primeinator 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!(n-k)!) though your point as to why if n is prime then neither k! or (n-k)! have n as a factor is lost on me though clearly the answer must be obvious. I did warn you... math knowledge has atrophied significantly and was not extremely robust to begin with.
I should have been more explicit: each of the factors of k! and (n-k)! are less than n which is assumed to be prime. n would not divide anything smaller. For example 7 does not divide 5!

Last fiddled with by paulunderwood on 2021-02-24 at 21:13

2021-02-24, 22:10   #8
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts

Quote:
 Originally Posted by paulunderwood I should have been more explicit: each of the factors of k! and (n-k)! are less than n which is assumed to be prime. n would not divide anything smaller. For example 7 does not divide 5!
That makes sense and reading on the nCk notation by definition n > k, which I was not aware of.

Quote:
 and so binom(n,k) must be divisible by the prime
I simplify nCk = n!/(k!(n-k)!) to (n-k+1)!/k! so this makes sense as well.

Last fiddled with by Primeinator on 2021-02-24 at 22:23

2021-02-24, 22:18   #9
paulunderwood

Sep 2002
Database er0rr

EAB16 Posts

Quote:
 Originally Posted by Primeinator That makes sense and reading on the nCk notation by definition n > k, which I was not aware of.
n! the numerator is divisible by n, but each of the factors of k! and (n-k)! are not.

Here is a concrete example 7!/(5!*2!). Here 7 divides 7! but not 5! or 2!

Last fiddled with by paulunderwood on 2021-02-24 at 22:26

2021-02-24, 22:32   #10
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts

Quote:
 Originally Posted by paulunderwood So working mod n all the binom are 0
Again, I am sorry for my idiocy and failure to grasp what should be basic algebra.

I understand (n-k+1)!/k! is divisible by n but I do not see how this = 0 (mod n)

2021-02-24, 22:52   #11
paulunderwood

Sep 2002
Database er0rr

5×751 Posts

Quote:
 Originally Posted by Primeinator Again, I am sorry for my idiocy and failure to grasp what should be basic algebra. I understand (n-k+1)!/k! is divisible by n but I do not see how this = 0 (mod n)
if it is divisible by n it leaves a remainder of 0 by division which by definition is 0 mod n. After all n divides 0.

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 2021-02-24 at 22:59

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Math 4 2013-04-01 02:39 jasong PrimeNet 3 2009-07-07 22:31 Damian Math 16 2007-11-05 14:55 mfgoode Science & Technology 5 2006-12-12 17:20 NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 17:17.

Tue Jul 27 17:17:40 UTC 2021 up 4 days, 11:46, 0 users, load averages: 2.40, 2.69, 2.75

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.