mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2020-05-10, 20:14   #1
ThomRuley
 
ThomRuley's Avatar
 
May 2003

24310 Posts
Default PRP testing

This appears to be a new step in the GIMPS process.

What exactly is it, and how does the math work?
ThomRuley is offline   Reply With Quote
Old 2020-05-10, 20:37   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

19×443 Posts
Default

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
Uncwilly is offline   Reply With Quote
Old 2020-05-10, 23:37   #3
ThomRuley
 
ThomRuley's Avatar
 
May 2003

35 Posts
Default

Does that mean we only do LL on exponents that pass PRP?
ThomRuley is offline   Reply With Quote
Old 2020-05-11, 00:10   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

19·443 Posts
Default

Quote:
Originally Posted by ThomRuley View Post
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.
Uncwilly is offline   Reply With Quote
Old 2020-05-11, 01:18   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,243 Posts
Default

Quote:
Originally Posted by ThomRuley View Post
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.
VBCurtis is offline   Reply With Quote
Old 2020-05-11, 15:12   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·232 Posts
Default

Quote:
Originally Posted by ThomRuley View Post
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
kriesel is online now   Reply With Quote
Old 2020-05-11, 16:23   #7
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×232 Posts
Default

The PRP/LL ratio was checked 6 months ago and described at https://www.mersenneforum.org/showpo...9&postcount=14
kriesel is online now   Reply With Quote
Old 2020-05-14, 07:22   #8
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

FB16 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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:
http://mersenneforum.org/showthread....22471&p=465431
kruoli is offline   Reply With Quote
Old 2020-05-16, 07:30   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·11·157 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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...
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness GP2 Wagstaff PRP Search 386 2020-08-09 03:02
Anti-poverty drug testing vs "high" tax deduction testing kladner Soap Box 3 2016-10-14 18:43
Testing.... kar_bon Raiders of the Lost Primes 257 2010-03-15 00:27
What am I testing? GARYP166 Information & Answers 9 2009-02-18 22:41
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53

All times are UTC. The time now is 04:38.

Wed Aug 12 04:38:19 UTC 2020 up 26 days, 25 mins, 1 user, load averages: 1.78, 1.91, 1.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.