mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-10-22, 02:19   #12
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

Quote:
Originally Posted by piforbreakfast View Post
So is an LL test the final step for determining a prime?
If you talk about mersenne numbers, yes. Moreover, for larger numbers over some size, LL is the only way to tell with certainty that the mersenne number is prime.

Last fiddled with by LaurV on 2021-10-22 at 02:21
LaurV is offline   Reply With Quote
Old 2021-10-22, 11:21   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·19·23 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.
I barely understand the necessity but would have to refer to the LL wiki page for sufficiency.
paulunderwood is offline   Reply With Quote
Old 2021-10-22, 16:54   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×5×7×73 Posts
Default

Quote:
Originally Posted by piforbreakfast View Post
So is an LL test the final step for determining a prime?
A PRP test can prove a number to be composite, but numbers that "pass" a PRP test can be composite. So if you want a proof of primality, you need more.

The LL test is determinative for whether Mersenne numbers are prime. It's not the only possible way of proving a Mersenne number to be prime, of course, but AFAIK it's the only known test of a large Mersenne number that can be completed in a reasonable length of time.

Trial division would work in theory, but is impracticable for all but very small exponents.
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-22, 18:06   #15
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×739 Posts
Default

For the full sequence summarized, see #35 of https://www.mersenneforum.org/showpost.php?p=521665&postcount=3
TF and P-1 are done opportunistically, to the amount of effort that minimizes average overall effort, then PRP/GEC/Proof gen, which almost always will show a Mersenne number composite. Any rare exception gets special attention.

Last fiddled with by kriesel on 2021-10-22 at 18:09
kriesel is online now   Reply With Quote
Old 2021-10-24, 14:36   #16
dov1093
 
Oct 2021
Israel

7 Posts
Default Avoiding time-consuming exponantiating

Let us just assume that - for a given p - 3^(2^p)=9 (mode Mp) and check the assumption by Pietrzak's verifier. If the verifier does not find that the equality is true, then Mp isn't prime. This is done without comuting 3^(2^p) (mode Mp)! So this procedure can save a very large amount of runnig-time!
dov1093 is offline   Reply With Quote
Old 2021-10-24, 16:06   #17
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

117668 Posts
Default

Quote:
Originally Posted by dov1093 View Post
<snip>
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).
<snip>
Please explain how to verify that 3^(2^p) == 3^2 (mod 2^p - 1) without computing 3^(2^p) (mod 2^p -1).
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-24, 16:54   #18
dov1093
 
Oct 2021
Israel

78 Posts
Default Pieterzak's verifier

Pieterzak published an algorithm that verifies if x^(2^t)=y (mode N) without computing x^(2^t) (mode N). The new PRP algorithm avoids double cheking by using this verifier.
dov1093 is offline   Reply With Quote
Old 2021-10-24, 17:09   #19
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·19·23 Posts
Default

Quote:
Originally Posted by dov1093 View Post
Pieterzak published an algorithm that verifies if x^(2^t)=y (mode N) without computing x^(2^t) (mode N). The new PRP algorithm avoids double cheking by using this verifier.
Do you have a link to the said publication?
paulunderwood is offline   Reply With Quote
Old 2021-10-24, 18:09   #20
dov1093
 
Oct 2021
Israel

710 Posts
Default Reference

https://allquantor.at/blockchainbib/...2018simple.pdf
dov1093 is offline   Reply With Quote
Old 2021-10-24, 18:32   #21
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F5D16 Posts
Default

Thanks for the link.

Isn't this what Prime95/mprime and gpuowl use already?
paulunderwood is offline   Reply With Quote
Old 2021-10-24, 19:31   #22
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·5·7·73 Posts
Default

Perhaps the OP thinks you can simply feed a proposed value (say 9) for 3^(2^p) (mod 2^p - 1) into the verifier, and be able to do a cheap computation to see whether it's right, without actually having to compute the value at all.

I'm not an expert, but I'm pretty sure it doesn't work that way.

As I understand it, what the verifier actually verifies is the original computation of the residue. It is the computation itself which generates the "verification file." No computation, no verification. The verifier does let you avoid having to recompute the value in order to verify it, which is how it used to be done. The new verification checks the computation with a fraction of a percent of the effort required for the actual computation.

Last fiddled with by Dr Sardonicus on 2021-10-28 at 02:28 Reason: w
Dr Sardonicus is offline   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 21:41.


Sun Nov 28 21:41:21 UTC 2021 up 128 days, 16:10, 0 users, load averages: 1.56, 1.48, 1.41

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.