mersenneforum.org  

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

Reply
 
Thread Tools
Old 2019-03-23, 19:03   #1
Runtime Error
 
Sep 2017
USA

23×52 Posts
Default 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:
https://www.mersenne.org/various/math.php
Runtime Error is offline   Reply With Quote
Old 2019-03-23, 21:11   #2
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5·13·89 Posts
Default

Quote:
Originally Posted by Runtime Error View Post
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:
https://www.mersenne.org/various/math.php
The number form makes the math much faster than for general numbers.

https://www.mersenneforum.org/showth...378#post468378
https://en.wikipedia.org/wiki/Fermat_pseudoprime
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).

Last fiddled with by kriesel on 2019-03-23 at 21:35
kriesel is online now   Reply With Quote
Old 2019-03-23, 21:43   #3
Runtime Error
 
Sep 2017
USA

C816 Posts
Default

Thank you, kriesel.

It's a shame that even this forum has scummy trolls.
Runtime Error is offline   Reply With Quote
Old 2019-03-24, 00:56   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23·32·139 Posts
Default

Quote:
Originally Posted by Runtime Error View Post
It's a shame that even this forum has scummy trolls.
And we have mods that take care of them.
Uncwilly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
understanding P-1/TF and the finding of factors dragonbud20 Information & Answers 5 2019-02-16 01:46
Understanding status info Idgo Information & Answers 9 2018-11-28 10:49
Understanding assignment rules Fred PrimeNet 3 2016-05-19 13:40
Understanding NFS Demonslay335 YAFU 11 2016-01-08 17:52
LL Test: Understanding the math zacariaz Homework Help 32 2007-05-16 15:18

All times are UTC. The time now is 22:08.


Thu Oct 21 22:08:26 UTC 2021 up 90 days, 16:37, 1 user, load averages: 1.90, 2.43, 2.42

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.