False primes

Is it possible to for LLR to report a prime when the number is really composite? I know the program has residues like:

LLR Res64: C858139A8DC5475D

when a number is tested, but is it possible for the residue of a composite number to be

LLR Res64: 0000000000000000

thus making it prime?

The odds of this are very small (16^16, since there are 16 digits and 16 hex numbers, 0-F), but it is possible, right?

[Kevin]

Originally Posted by Unregistered

is it possible for the residue of a composite number to be

LLR Res64: 0000000000000000

thus making it prime?

Well I mean, the number is prime or it is composite. So that doesn't really make much sense.

The theorem that the LL-test is based on says that the Mersenne number is prime if and only if the last step gives 0. So assuming no computer errors, the last step of the test for a composite number will give a non-zero result. However, the last step is generally a gigantic number (we're talking millions of digits). To keep things simpler, just the last 16 or so digits in hex are reported, and that's called the residue. Unless there's some mathematical reason I'm not aware of, it would be possible for the residue of the last step to be 16 zeros, even if the last step in its entirety isn't zero.

[davieddy]

My guess is that the full residue is checked when the
last 16 hexdigits are found to be 0.

[Mr. P-1]

GIMPS has had one false positive which was the product of a data corruption during the run. As a result, the client was modified to better detect such conditions.

is it possible for the residue of a composite number to be

LLR Res64: 0000000000000000

thus making it prime?

Originally Posted by Kevin

Well I mean, the number is prime or it is composite. So that doesn't really make much sense.

The question wasn't too clear on this, but I assume that he meant something like:

"Number N is composite, but the last few digits of the (non-zero) residue are 0000000000000000. Therefore, the program thinks that it's prime, but it's really composite."

it would be possible for the residue of the last step to be 16 zeros, even if the last step in its entirety isn't zero.

So, is the full residue checked when the last 16 hex digits are all 0?

[ewmayer]

I can't speak for George's Prime95 code, but the typical end-of-test processing sequence is as follows:

1. Check the full residue vector, if zero print "Mxxx is prime". otherwise print "Mxxx is not prime";

2. Print low 64 bits of residue; along with lots of exciting !!! if (1) indicates prime.

Thus, there is a roughly 1 in 2^64 chance of the number being not prime but the low 64 bits of the residue happening to be zero. However, as long as one does indeed check the full residue as described above, the number will still be properly flagged as "not prime". Since the primenet server, however, uses the 64-bit residue, unless there are other checksums it uses in addition, the server might well incorrectly flag such a case as "prime." However, the standard perusal of the user's log file done as part of the new-prime verification process would quickly reveal the not-prime-but-Res64-zero issue.

One solution, if for some reason it proved desirable to eliminate even the one in 2^64 odds, would be to also compute some other residue-based checksums such as the Selfridge-Hurwitz residues computed as part of Fermat number testing, where we also compute the residue modulo 2^35-1 and 2^36-1. Those would reduce the odds of such a "false positive" by additional multiplicative factors of roughly 1/2^35 and 1/2^36, respectively.

[Uncwilly]

Originally Posted by ewmayer

However, the standard perusal of the user's log file done as part of the new-prime verification process would quickly reveal the not-prime-but-Res64-zero issue.

One solution, if for some reason it proved desirable to eliminate even the one in 2^64 odds, would be to also compute some other residue-based checksums

Why not have the program send a sum of the digits of the entire residual (one could continue this down to a single 2 digit hex number, if desired).

[Batalov]

Originally Posted by Unregistered

The question wasn't too clear on this, but I assume that he meant something like:

"Number N is composite, but the last few digits of the (non-zero) residue are 0000000000000000. Therefore, the program thinks that it's prime, but it's really composite."

So, is the full residue checked when the last 16 hex digits are all 0?

Yes, it is (in Prime95). See the commonb.c, function generateResidue64(). It's opensource (except the reporting code plug-in). See the website.

In fact, the residue is converted into a giant format, in which 0 is simply a giant number of bitlength 0 (tmp->sign==0), but all other numbers have non-zero length (and the sign, which is collapsed together with bitlength). A real 0 residue is recognized and is reported as prime, a 0000000000000000 is possible but will be accompanied with the "1" return code. So Prime95 in this unlikely (<1/10^19) event will report

UID: Batman/microwave, M86882639 is not prime. Res64: 0000000000000000. Wd1: 308059C5,33263648,00000000, AID: C6D56AD38B022B7614BC2F476577A899

(or smth like that)...

Don't know about LLR, but I'd assume that the treatment would be similar - they share the libgwnum and some code, don't they?

[Batalov]

P.S. (too late to edit)
Yes, out of curiosity I've looked in LLR 3.7.1b source and the treatment is the same. The output line will say "... is not prime".

If you set OldRes64=1 in the INI file, then you will also get the OLD64 residue; the probability of both of these to have only zeroes is ridiculously low ... or actually don't forget that they are far from being independent; OLD64 := RES64 * 3 - 3 (mod N), so if RES64 happens to be 1(mod 2^64) and its upper (far, far right) few bit(s) are zero, then it would look quite like a "prime" report ...
But still, never mind that, just look for the words "not prime".

P.P.S. For LLR test, the (probable) prime will generate a residue of 0000000000000001, actually (not zeroes), and the OLD64 will be 0000000000000000. But it will print "... prime", instead.