20190323, 19:03  #1 
Sep 2017
USA
2^{3}×5^{2} Posts 
Understanding Mersenne PRP
Since PRP testing has become the new primality testing workhorse of this project, I'm interested in learning more about it. As math undergrad and nonmath PhD, I understand the basics. However, none of the theorems that I've encountered say anything special about Mersenne numbers and PRP. I'd greatly appreciate it if someone could point me in the right direction. (I could have easily missed something.)
My question: Is there anything *special* about implementing a probable primality test for numbers of the form 2^P1? That is, is it different than PRPing any old number? Note: I understand that PRP has astronomically low error rates compared to LL, & that Prime95 is very good at multiplying big numbers, etc. Also, if the answer is simple enough, perhaps someone could update "The Math" page: https://www.mersenne.org/various/math.php 
20190323, 21:11  #2  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5·13·89 Posts 
Quote:
https://www.mersenneforum.org/showth...378#post468378 https://en.wikipedia.org/wiki/Fermat_pseudoprime Consider how to compute x mod q1 quickly, when q is a power of 2, and the computation occurs in binary. Compute 24 mod 7 (11000 mod 111). 11 000 >011 done. 125 mod 31 (11 11101 mod 11111) 11+11101 >1 00000 > 1 done. Or, quick, what's the remainder of 93169 divided by 9? It's not that the PRP computation is inherently lower error than LL. They're probably pretty close, on the same hardware, in raw error rate. It's that PRP allows use of the Gerbicz check which has quite high error detection rate, while LL to our knowledge allows only the ~50% error detection rate by occasional evaluation of the Jacobi symbol. Both Gerbicz check and Jacobi check application to GIMPS are relatively recent developments. Some GIMPS applications have not incorporated the latest relevant check yet (CUDALucas, clLucas, gpulucas, glucas). Last fiddled with by kriesel on 20190323 at 21:35 

20190323, 21:43  #3 
Sep 2017
USA
C8_{16} Posts 
Thank you, kriesel.
It's a shame that even this forum has scummy trolls. 
20190324, 00:56  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2^{3}·3^{2}·139 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
understanding P1/TF and the finding of factors  dragonbud20  Information & Answers  5  20190216 01:46 
Understanding status info  Idgo  Information & Answers  9  20181128 10:49 
Understanding assignment rules  Fred  PrimeNet  3  20160519 13:40 
Understanding NFS  Demonslay335  YAFU  11  20160108 17:52 
LL Test: Understanding the math  zacariaz  Homework Help  32  20070516 15:18 