mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2021-02-24, 23:12   #12
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5×19×53 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
But a poster here, R. Gerbicz, came up with an improvement to the Lucas-Lehmer test that essentially allows it to (1) back up its progress every so often and (2) either prove that it has (whp?) made no errors since the last backup, or else go back to said backup and start over. Even better, the overhead to this new test (we call it the PRP test or the Gerbicz test) is less than 1%, compared to a double check at 100%. So switching can make the project go a lot faster.
Not exactly. Maybe I'm badly misunderstanding you, but I see it as at least 4 distinct developments, one leading to the next. (I apologize for any errors or omissions in the following.)

Mihai Preda had an unreliable gpu and wrote a variant of early gpuowl that did segments of the LL sequence twice and compared them (which IIRC he called "supersafe").

Forum user Error identified the Jacobi symbol check for the LL sequence. Because of its high cost it's done only rarely and it has a ~50% chance of detecting that an error has occurred. This I believe led some to search for more reliable / definitive error checks. Its implementation was quick and added ~0.3% to run times.

Robert Gerbicz identified a way to provide a superior check (GEC, Gerbicz Error Check) that applies to the probably prime test but not to the LL sequence, detecting essentially 100% of errors, which enables reliable retreat after a failed GEC to the most recent saved state that passed a GEC. At this point there was a debate over whether full double checks of PRP results were necessary.
Most of the major GIMPS primality testing software also quickly adopted the PRP/GEC rather quickly (Gpuowl, prime95, mprime, Mlucas)

https://www.mersenne.org/ describes the effect of the third piece of progress, the VDF applied to the whole PRP primality test. See also https://mersenneforum.org/showthread.php?t=25638
This was added last year to Gpuowl, prime95, mprime, and is planned for Mlucas.The PrimeNet server was modified too, to accept new format PRP result records and proof files from client software, and issue certification assignments to mprime/prime95 and accept certification results, keep track of new work types and the computing credit for them, etc.

More recently, some of the error checking has been applied to P-1 factoring also. Partly by combining stage 1 P-1 with early PRP iterations protected by the GEC, and partly by applying the Jacobi check, in gpuowl v7.x, along with other older techniques, such as detecting zeroed-residue.

Last fiddled with by kriesel on 2021-02-24 at 23:12
kriesel is online now   Reply With Quote
Old 2021-02-25, 01:15   #13
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10010100001012 Posts
Default

Quote:
Originally Posted by Primeinator View Post
I simplify nCk = n!/(k!(n-k)!) to (n-k+1)!/k! so this makes sense as well.
I think you should review this simplification again- I don't think your formula is accurate.
VBCurtis is offline   Reply With Quote
Old 2021-02-25, 01:20   #14
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I think you should review this simplification again- I don't think your formula is accurate.
You are correct. This is an error. Can this factorial expression be simplified?

Edit: nice mega Pidgeot

Last fiddled with by Primeinator on 2021-02-25 at 01:32
Primeinator is offline   Reply With Quote
Old 2021-02-25, 02:24   #15
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

32×13 Posts
Default

I don't want to hijack this thread, but can anyone tell me if the PRP test conclusively proves a number is prime, or only that it is probably prime, as the name suggests? If it is only probably, what is the probability of an exponent around 120,000,000 or 330,000,000 being detected as prime, when in fact is is not?

I believe the Lucas-Lemar test gives a definitive prime/composite answer.

I'm ignoring hardware or software errors.

Last fiddled with by drkirkby on 2021-02-25 at 02:26
drkirkby is offline   Reply With Quote
Old 2021-02-25, 03:14   #16
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts
Default

Quote:
Originally Posted by drkirkby View Post
but can anyone tell me if the PRP test conclusively proves a number is prime, or only that it is probably prime, as the name suggests? If it is only probably, what is the probability of an exponent around 120,000,000 or 330,000,000 being detected as prime, when in fact is is not?

I believe the Lucas-Lemar test gives a definitive prime/composite answer.

I'm ignoring hardware or software errors.
The PRP test does not give a definitive answer on primality but can tell you a number is composite. Proving primality must be done by the LL. Someone more knowledgeable than myself can answer your other questions.

Last fiddled with by Primeinator on 2021-02-25 at 03:15
Primeinator is offline   Reply With Quote
Old 2021-02-25, 03:24   #17
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

11×431 Posts
Default

A mersenne prp is 99.999+% likely to be prime. It would be a much more important discovery to find a mersenne prp that isn't actually prime than it would be to find a new mersenne prime.

LL testing at 100M+ exponents is about 2% likely to have an error. Prp testing is more than 100 times less likely to have an error. So, "ignoring hardware or software errors" is, unfortunately, where all the chance of "not actually prime" occurs.

The prp test has checks for errors, which is why it's the only test we use going forward.
VBCurtis is offline   Reply With Quote
Old 2021-02-25, 03:44   #18
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

60078 Posts
Default

Quote:
Originally Posted by drkirkby View Post
I don't want to hijack this thread, but can anyone tell me if the PRP test conclusively proves a number is prime, or only that it is probably prime, as the name suggests? If it is only probably, what is the probability of an exponent around 120,000,000 or 330,000,000 being detected as prime, when in fact is is not?

I believe the Lucas-Lemar test gives a definitive prime/composite answer.

I'm ignoring hardware or software errors.
No, but PRP tests can conclusively prove a number is composite (barring hardware/software errors), so we only need LL tests IF the PRP test says the number is a probable prime.
This has not happened yet, since all Mersenne Primes has been found by LL tests so far, before PRP test became the most common test.
ATH is offline   Reply With Quote
Old 2021-02-25, 05:20   #19
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·1,877 Posts
Default

.
Offtopic, about thread title.

There is nothing "moronic" about asking, and we (engineers, math/technical guys, geeks, etc.) love humble questions and love the people who sincerely want to learn. Having less knowledge about some subject is not wrong or despicable. Nobody in the world knows all about everything. Having the courage to ask questions and learn is commendable. What's bad is repeating the same mistakes forever, and refusing to learn from them. We hate those people who are ignorant, arrogant, and stubborn to stay ignorant, in the same time.

Therefore, I changed the thread title to get rid of the "moronic" words. I don't know if OP posted it like that from the start (I call myself bad words when I am angry on my own stupidity, which actually happens quite often), or some funny moderator changed it, but if the later, then it was a bad joke.

Sorry for offtopic, I only read the first few posts, I continue reading and I may post something which is not offtopic, if the other posters didn't already say everything I could comment about the subject.
.

Last fiddled with by LaurV on 2021-02-25 at 05:36
LaurV is offline   Reply With Quote
Old 2021-02-25, 14:39   #20
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts
Default

Quote:
Originally Posted by LaurV View Post
.
Offtopic, about thread title.

There is nothing "moronic" about asking, and we (engineers, math/technical guys, geeks, etc.) love humble questions and love the people who sincerely want to learn. Having less knowledge about some subject is not wrong or despicable. Nobody in the world knows all about everything. Having the courage to ask questions and learn is commendable. What's bad is repeating the same mistakes forever, and refusing to learn from them. We hate those people who are ignorant, arrogant, and stubborn to stay ignorant, in the same time.

Therefore, I changed the thread title to get rid of the "moronic" words. I don't know if OP posted it like that from the start (I call myself bad words when I am angry on my own stupidity, which actually happens quite often), or some funny moderator changed it, but if the later, then it was a bad joke.

Sorry for offtopic, I only read the first few posts, I continue reading and I may post something which is not offtopic, if the other posters didn't already say everything I could comment about the subject.
.
I'm into self-deprecation and/or am jaded by asking questions on this forum years ago and reading responses from Dr. Silverman.
I sincerely appreciate the responses from people on this forum so far to my question on PRP testing. I need to work with the examples provided so try and make the leap from applying the binomial theorem to the PRP test. I do wish to understand the "why" and "how" of the PRP test but it takes me longer to understand the mathematics than for most other people on this form. While I enjoy math it was never my strongest subject and my field of expertise is very different (biology/medicine).
Primeinator is offline   Reply With Quote
Old 2021-02-25, 15:01   #21
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

224318 Posts
Default

Quote:
Originally Posted by Primeinator View Post
I'm into self-deprecation and/or am jaded by asking questions on this forum years ago and reading responses from Dr.[sic] Silverman.
Bob, RDS, Mr. Silverman, that old crotchety guy, whatever you call him, is not around the forum any more to blast people.
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New fundamental result in PDEs ewmayer Math 4 2013-04-01 02:39
Forcing testing of F14[2^(2^14)+1] question jasong PrimeNet 3 2009-07-07 22:31
I generalized the fundamental theorem of calculus Damian Math 16 2007-11-05 14:55
Fundamental particle found with no charge. mfgoode Science & Technology 5 2006-12-12 17:20
newbie question - testing primality of very large numbers NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 20:52.

Wed Apr 21 20:52:11 UTC 2021 up 13 days, 15:33, 0 users, load averages: 1.08, 1.49, 1.70

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.