mersenneforum.org PRP testing
 Register FAQ Search Today's Posts Mark Forums Read

 2020-05-10, 20:14 #1 ThomRuley     May 2003 F816 Posts PRP testing This appears to be a new step in the GIMPS process. What exactly is it, and how does the math work?
 2020-05-10, 20:37 #2 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 2·4,787 Posts PRP is a different way of checking if a number is prime or not. It is not conclusive, but is good enough in most cases. It takes about the same time to do as LL testing. But, with the error checking that has been applied, it is less likely that we will miss a prime during first time checking. It is also less likely that an exponent will need a triple check. https://en.wikipedia.org/wiki/Probable_prime If a number passes the PRP test, then the normal LL checks will be done to prove that the number is prime. I believe that Prime95 uses a version of the Miller-Rabin test https://www.rieselprime.de/ziki/Mill...primality_test
 2020-05-10, 23:37 #3 ThomRuley     May 2003 23·31 Posts Does that mean we only do LL on exponents that pass PRP?
2020-05-11, 00:10   #4
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2×4,787 Posts

Quote:
 Originally Posted by ThomRuley Does that mean we only do LL on exponents that pass PRP?
Any exponent that had a First Time check doing LL should have an LL DC. Other than that, the rule of thumb is to use PRP for all new First Time checks and to DC those that have PRP for a first time check.

TLDR; Yes. It is preferred.

2020-05-11, 01:18   #5
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

24·13·23 Posts

Quote:
 Originally Posted by ThomRuley Does that mean we only do LL on exponents that pass PRP?
Right! If the prp test shows composite, there is no reason to do an LL test.

If the prp test shows probable prime, we do an LL test to confirm the discovery- we do not expect to ever find a mersenne candidate that is prp but not actually prime.

2020-05-11, 15:12   #6
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

22×3×7×61 Posts

Quote:
 Originally Posted by ThomRuley Does that mean we only do LL on exponents that pass PRP?
Ideally yes, since the PRP test is protected by the excellent Gerbicz error check But many systems have not been switched over from the traditional LL test (protected by the 50% error detection rate Jacobi symbol check in prime95, mprime, mlucas, but not in cudalucas or recent versions of gpuowl). LL tests are much more prone to needing triple-checks because of their approximately 2% error rate. PRP tests are backed up a bit and retried when a error is detected by the Gerbicz check, so PRP final results are almost guaranteed to be correct the first time. Almost.
Last time I checked, the LL/PRP first test mix was about 50-50.

Last fiddled with by kriesel on 2020-05-11 at 15:13

 2020-05-11, 16:23 #7 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 512410 Posts The PRP/LL ratio was checked 6 months ago and described at https://www.mersenneforum.org/showpo...9&postcount=14
2020-05-14, 07:22   #8
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

32·5·11 Posts

Quote:
 Originally Posted by Uncwilly I believe that Prime95 uses a version of the Miller-Rabin test https://www.rieselprime.de/ziki/Mill...primality_test
Gerbicz error checking requires a Fermat test, see his original post:

2020-05-16, 07:30   #9
LaurV
Romulan Interpreter

Jun 2011
Thailand

3×47×67 Posts

Quote:
 Originally Posted by VBCurtis If the prp test shows probable prime, we do an LL test to confirm the discovery- we do not expect to ever find a mersenne candidate that is prp but not actually prime.
In fact, finding a mersenne PSP (pseudoprime, i.e. it is PRP, but composite) will make a lot more sensation and bring you more fame than finding a new prime, even if that is only base 3. We know few dozens mersenne primes, but no PSP yet...

 Similar Threads Thread Thread Starter Forum Replies Last Post GP2 Wagstaff PRP Search 414 2020-12-27 08:11 kladner Soap Box 3 2016-10-14 18:43 kar_bon Raiders of the Lost Primes 257 2010-03-15 00:27 GARYP166 Information & Answers 9 2009-02-18 22:41 eepiccolo Math 6 2006-03-28 20:53

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

Fri May 14 14:24:19 UTC 2021 up 36 days, 9:05, 0 users, load averages: 2.30, 2.05, 2.01