Fundamental Question(s) on PRP Testing

[Primeinator]

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!

[CRGreathouse]

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.

[Primeinator]

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".

[paulunderwood]

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.

[paulunderwood]

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.

[Primeinator]

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.

[paulunderwood]

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!

[Primeinator]

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.

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.

[paulunderwood]

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!

[Primeinator]

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)

[paulunderwood]

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.