mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-10-18, 13:39   #1
dov1093
 
Oct 2021
Israel

78 Posts
Default 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.
dov1093 is offline   Reply With Quote
Old 2021-10-18, 13:53   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

175810 Posts
Default

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
Nick is offline   Reply With Quote
Old 2021-10-18, 14:11   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 Posts
Default

Quote:
Originally Posted by Nick View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-10-18, 14:23   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

6DE16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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!
Nick is offline   Reply With Quote
Old 2021-10-18, 14:59   #5
axn
 
axn's Avatar
 
Jun 2003

143B16 Posts
Default

Isn't the PRP certification based on Pieterzak?

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

IOW, been there, done that ?!
axn is offline   Reply With Quote
Old 2021-10-18, 16:54   #6
dov1093
 
Oct 2021
Israel

716 Posts
Default 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!
dov1093 is offline   Reply With Quote
Old 2021-10-19, 10:42   #7
dov1093
 
Oct 2021
Israel

7 Posts
Default 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.
dov1093 is offline   Reply With Quote
Old 2021-10-19, 11:50   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2021-10-22, 01:08   #9
piforbreakfast
 
Oct 2020
Terre Haute, IN

25·3 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
piforbreakfast is offline   Reply With Quote
Old 2021-10-22, 01:11   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

Quote:
Originally Posted by piforbreakfast View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-10-22, 01:14   #11
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

273A16 Posts
Default

Quote:
Originally Posted by piforbreakfast View Post
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
chalsall is online now   Reply With Quote
Reply

Thread Tools


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

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


Tue Nov 30 15:59:43 UTC 2021 up 130 days, 10:28, 0 users, load averages: 2.58, 1.56, 1.45

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.