Fundamental Question(s) on PRP Testing

[kriesel]

Originally Posted by CRGreathouse

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.

[VBCurtis]

Originally Posted by Primeinator

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.

[Primeinator]

Originally Posted by VBCurtis

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

[drkirkby]

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.

[Primeinator]

Originally Posted by drkirkby

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.

[VBCurtis]

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.

[ATH]

Originally Posted by drkirkby

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.

[LaurV]

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

[Primeinator]

Originally Posted by LaurV

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

[Uncwilly]

Originally Posted by Primeinator

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.