mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-02-24, 19:40   #1
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts
Default 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
Primeinator is offline   Reply With Quote
Old 2021-02-24, 20:24   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176116 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2021-02-24, 20:35   #3
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Primeinator is offline   Reply With Quote
Old 2021-02-24, 20:36   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×67 Posts
Default

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 is offline   Reply With Quote
Old 2021-02-24, 20:49   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·33·67 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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.
paulunderwood is offline   Reply With Quote
Old 2021-02-24, 21:06   #6
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
Primeinator is offline   Reply With Quote
Old 2021-02-24, 21:10   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×67 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-02-24, 22:10   #8
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
Primeinator is offline   Reply With Quote
Old 2021-02-24, 22:18   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·33·67 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-02-24, 22:32   #10
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

11100100112 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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)
Primeinator is offline   Reply With Quote
Old 2021-02-24, 22:52   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110001000102 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 11:19.

Fri Apr 16 11:19:28 UTC 2021 up 8 days, 6 hrs, 0 users, load averages: 1.82, 1.67, 1.64

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.