mersenneforum.org a stupid question re: primality of mp
 Register FAQ Search Today's Posts Mark Forums Read

 2021-10-18, 13:39 #1 dov1093   Oct 2021 Israel 78 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.
 2021-10-18, 13:53 #2 Nick     Dec 2012 The Netherlands 2·3·293 Posts If $$M_p=2^p-1$$ is prime then, for all integers n not divisible by $$M_p$$, $$n^{2^p-2}\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 2021-10-18 at 14:23 Reason: Typo
2021-10-18, 14:11   #3
paulunderwood

Sep 2002
Database er0rr

2·7·281 Posts

Quote:
 Originally Posted by Nick If $$M_p=2^p-1$$ is prime then, for all integers n not divisible by $$M_p$$, $$n^{2^p}\equiv 1\pmod{M_p}$$ by Fermat's little theorem.
Err, Nick, n^2^p would be n^2 mod Mp. Usually we use "a" not "n" and n=2^p-1.

Last fiddled with by paulunderwood on 2021-10-18 at 14:12

2021-10-18, 14:23   #4
Nick

Dec 2012
The Netherlands

110110111102 Posts

Quote:
 Originally Posted by paulunderwood Err, Nick, n^2^p would be n^2 mod Mp. Usually we use "a" not "n" and n=2^p-1.
Yes, a typo - thanks!

 2021-10-18, 14:59 #5 axn     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 ?!
 2021-10-18, 16:54 #6 dov1093   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!
 2021-10-19, 10:42 #7 dov1093   Oct 2021 Israel 710 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.
 2021-10-19, 11:50 #8 paulunderwood     Sep 2002 Database er0rr 2×7×281 Posts We do a 3-PRP test because it uses a very reliable Gerbicz Error Correcting algorithm. If a Mersenne number is found to be 3-PRP we then proceed to an LL test. The chances of a 3-PRP not passing an LL test are infinitesimal, though not known to be zero.
2021-10-22, 01:08   #9
piforbreakfast

Oct 2020
Terre Haute, IN

1408 Posts

Quote:
 Originally Posted by paulunderwood We do a 3-PRP test because it uses a very reliable Gerbicz Error Correcting algorithm. If a Mersenne number is found to be 3-PRP we then proceed to an LL test. The chances of a 3-PRP not passing an LL test are infinitesimal, though not known to be zero.
So is an LL test the final step for determining a prime?

2021-10-22, 01:11   #10
paulunderwood

Sep 2002
Database er0rr

2·7·281 Posts

Quote:
 Originally Posted by piforbreakfast So is an LL test the final step for determining a prime?
The LL test is performed with different hardware and different software for 100% confidence,

Last fiddled with by paulunderwood on 2021-10-22 at 01:12

2021-10-22, 01:14   #11
chalsall
If I May

"Chris Halsall"
Sep 2002

1004210 Posts

Quote:
 Originally Posted by piforbreakfast So is an LL test the final step for determining a prime?
It depends on the situation.

Do you have a proof? Or only a supposition?

Edit: Sorry... Cross-posted with Paul. He understands the maths much better than I do.

Last fiddled with by chalsall on 2021-10-22 at 01:16

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Information & Answers 14 2015-06-18 23:37 Uncwilly Lounge 19 2013-03-07 04:44 Biggles Prime Sierpinski Project 3 2006-02-07 22:50 rpropper GMP-ECM 15 2005-11-14 14:43 fropones Math 2 2003-05-28 00:44

All times are UTC. The time now is 15:58.

Tue Nov 30 15:58:38 UTC 2021 up 130 days, 10:27, 0 users, load averages: 1.14, 1.26, 1.35

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.