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 non-math 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^P-1? 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:
[url]https://www.mersenne.org/various/math.php[/url]

[QUOTE=Runtime Error;511544]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 non-math 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^P-1? 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:
[URL]https://www.mersenne.org/various/math.php[/URL][/QUOTE]
The number form makes the math much faster than for general numbers.

[URL]https://www.mersenneforum.org/showthread.php?p=468378#post468378[/URL]
[URL]https://en.wikipedia.org/wiki/Fermat_pseudoprime[/URL]
Consider how to compute x mod q-1 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).

Thank you, kriesel.

It's a shame that even this forum has scummy trolls.

[QUOTE=Runtime Error;511586]It's a shame that even this forum has scummy trolls.[/QUOTE]And we have mods that take care of them.