20211018, 13:39  #1 
Oct 2021
Israel
7_{8} Posts 
a stupid question re: primality of mp
If mp is prime then we have n^(2^p)=n^2 (mod mp) for integer n.
To check primality of mp we may usu Pieterzak's verifer to verify 3^(2^p)=9 (mod mp). This can be done without the lengthy computation of 3^(2^p). If the verifer's result is negative then mp is not prime and if it is positive we check 5^(2^p)= 25 or go directly to LL. 
20211018, 13:53  #2 
Dec 2012
The Netherlands
2·3·293 Posts 
If \(M_p=2^p1\) is prime then, for all integers n not divisible by \(M_p\), \(n^{2^p2}\equiv 1\pmod{M_p}\) by Fermat's little theorem.
It is standard to use modulo arithmetic during the exponentiation. I do not immediately see what Pietrzak would add to that. Last fiddled with by Nick on 20211018 at 14:23 Reason: Typo 
20211018, 14:11  #3 
Sep 2002
Database er0rr
2·7·281 Posts 
Err, Nick, n^2^p would be n^2 mod Mp. Usually we use "a" not "n" and n=2^p1.
Last fiddled with by paulunderwood on 20211018 at 14:12 
20211018, 14:23  #4 
Dec 2012
The Netherlands
11011011110_{2} Posts 

20211018, 14:59  #5 
Jun 2003
5,179 Posts 
Isn't the PRP certification based on Pieterzak?
https://www.mersenneforum.org/showthread.php?t=24654 IOW, been there, done that ?! 
20211018, 16:54  #6 
Oct 2021
Israel
7 Posts 
speeding up
PRP computes 3^(2^P) and then verifies the result. We suggest avoiding this computatin, which lasts for almost all the running time. This avoidance can speed up the search for prime Mp by an order of magnitude!

20211019, 10:42  #7 
Oct 2021
Israel
7_{10} Posts 
Accelerating PRP
Pietrzak's algorithm verifies if x^(2^t)=y (mode N) without actually calculating the exponent.
If Mp is prime then  by Fermat little theorm  n^(2^p)=n^2 (mode Mp). The PRP algorithm computes 3^(2^p) (mode Mp) and then uses Pietrzak's verifier to find if the computatin has no error. But we don't need the very lengthy computation  all we need is to use the verifier to check if 3^(2^p)=9 (mode Mp). If it is false, then Mp isn't prime. If it is true let us try 5^(2^p)= 25 (mode Mp) and if it is also true we can go the LL algorithm. 
20211019, 11:50  #8 
Sep 2002
Database er0rr
2×7×281 Posts 
We do a 3PRP test because it uses a very reliable Gerbicz Error Correcting algorithm. If a Mersenne number is found to be 3PRP we then proceed to an LL test. The chances of a 3PRP not passing an LL test are infinitesimal, though not known to be zero.

20211022, 01:08  #9 
Oct 2020
Terre Haute, IN
140_{8} Posts 
So is an LL test the final step for determining a prime?

20211022, 01:11  #10 
Sep 2002
Database er0rr
2·7·281 Posts 
The LL test is performed with different hardware and different software for 100% confidence,
Last fiddled with by paulunderwood on 20211022 at 01:12 
20211022, 01:14  #11 
If I May
"Chris Halsall"
Sep 2002
Barbados
10042_{10} Posts 
It depends on the situation.
Do you have a proof? Or only a supposition? Edit: Sorry... Crossposted with Paul. He understands the maths much better than I do. Last fiddled with by chalsall on 20211022 at 01:16 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Stupid question reloaded  LaurV  Information & Answers  14  20150618 23:37 
There is no such thing as a stupid question?  Uncwilly  Lounge  19  20130307 04:44 
Possibly stupid question about PRP.  Biggles  Prime Sierpinski Project  3  20060207 22:50 
probably a stupid newbie question...  rpropper  GMPECM  15  20051114 14:43 
Stupid Question  fropones  Math  2  20030528 00:44 