a stupid question re: primality of mp

dov1093 · 2021-10-18, 13:39

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.

Nick · 2021-10-18, 13:53

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.

paulunderwood · 2021-10-18, 14:11

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.

Nick · 2021-10-18, 14:23

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!

axn · 2021-10-18, 14:59

Isn't the PRP certification based on Pieterzak?

https://www.mersenneforum.org/showthread.php?t=24654

IOW, been there, done that ?!

dov1093 · 2021-10-18, 16:54

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!

dov1093 · 2021-10-19, 10:42

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.

paulunderwood · 2021-10-19, 11:50

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.

piforbreakfast · 2021-10-22, 01:08

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?

paulunderwood · 2021-10-22, 01:11

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,

chalsall · 2021-10-22, 01:14

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.

2021-10-18, 13:39	#1
dov1093 Oct 2021 Israel 7 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 41×43 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, 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 7₁₀ 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Stupid question reloaded	LaurV	Information & Answers	14	2015-06-18 23:37
There is -no- such thing as a stupid question?	Uncwilly	Lounge	19	2013-03-07 04:44
Possibly stupid question about PRP.	Biggles	Prime Sierpinski Project	3	2006-02-07 22:50
probably a stupid newbie question...	rpropper	GMP-ECM	15	2005-11-14 14:43
Stupid Question	fropones	Math	2	2003-05-28 00:44

2021-10-18, 14:59	#5
axn Jun 2003 2⁸·3·7 Posts	Isn't the PRP certification based on Pieterzak? https://www.mersenneforum.org/showthread.php?t=24654 IOW, been there, done that ?!

2021-10-19, 11:50	#8
paulunderwood Sep 2002 Database er0rr 106A₁₆ 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.