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

2021-10-22, 02:19   #12
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·613 Posts

Quote:
 Originally Posted by piforbreakfast 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

2021-10-22, 11:21   #13
paulunderwood

Sep 2002
Database er0rr

32·19·23 Posts

Quote:
 Originally Posted by chalsall 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.

2021-10-22, 16:54   #14
Dr Sardonicus

Feb 2017
Nowhere

2×5×7×73 Posts

Quote:
 Originally Posted by piforbreakfast 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.

 2021-10-22, 18:06 #15 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 23×739 Posts 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
 2021-10-24, 14:36 #16 dov1093   Oct 2021 Israel 7 Posts 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!
2021-10-24, 16:06   #17
Dr Sardonicus

Feb 2017
Nowhere

117668 Posts

Quote:
 Originally Posted by dov1093 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).
Please explain how to verify that 3^(2^p) == 3^2 (mod 2^p - 1) without computing 3^(2^p) (mod 2^p -1).

 2021-10-24, 16:54 #18 dov1093   Oct 2021 Israel 78 Posts 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.
2021-10-24, 17:09   #19
paulunderwood

Sep 2002
Database er0rr

32·19·23 Posts

Quote:
 Originally Posted by dov1093 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?

 2021-10-24, 18:09 #20 dov1093   Oct 2021 Israel 710 Posts Reference
 2021-10-24, 18:32 #21 paulunderwood     Sep 2002 Database er0rr F5D16 Posts Thanks for the link. Isn't this what Prime95/mprime and gpuowl use already?
 2021-10-24, 19:31 #22 Dr Sardonicus     Feb 2017 Nowhere 2·5·7·73 Posts 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

 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 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