20211022, 02:19  #12 
Romulan Interpreter
"name field"
Jun 2011
Thailand
23120_{8} Posts 
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 20211022 at 02:21 
20211022, 11:21  #13  
Sep 2002
Database er0rr
7536_{8} Posts 
Quote:


20211022, 16:54  #14 
Feb 2017
Nowhere
12002_{8} Posts 
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. 
20211022, 18:06  #15 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5918_{10} Posts 
For the full sequence summarized, see #35 of https://www.mersenneforum.org/showpost.php?p=521665&postcount=3
TF and P1 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 20211022 at 18:09 
20211024, 14:36  #16 
Oct 2021
Israel
111_{2} Posts 
Avoiding timeconsuming 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 runnigtime!

20211024, 16:06  #17 
Feb 2017
Nowhere
5122_{10} Posts 

20211024, 16:54  #18 
Oct 2021
Israel
7 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.

20211024, 17:09  #19 
Sep 2002
Database er0rr
2·7·281 Posts 

20211024, 18:09  #20 
Oct 2021
Israel
111_{2} Posts 
Reference

20211024, 18:32  #21 
Sep 2002
Database er0rr
2×7×281 Posts 
Thanks for the link.
Isn't this what Prime95/mprime and gpuowl use already? 
20211024, 19:31  #22 
Feb 2017
Nowhere
2×13×197 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 20211028 at 02:28 Reason: w 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Stupid question reloaded  LaurV  Information & Answers  14  20150618 23:37 
There is no such thing as a stupid question?  Uncwilly  Lounge  19  20130307 04:44 
Possibly stupid question about PRP.  Biggles  Prime Sierpinski Project  3  20060207 22:50 
probably a stupid newbie question...  rpropper  GMPECM  15  20051114 14:43 
Stupid Question  fropones  Math  2  20030528 00:44 