mersenneforum.org False primes
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-20, 05:37 #1 Unregistered   161016 Posts 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?
2009-01-20, 11:46   #2
Kevin

Aug 2002
Ann Arbor, MI

1B116 Posts

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

 2009-01-20, 16:10 #3 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts My guess is that the full residue is checked when the last 16 hexdigits are found to be 0.
 2009-01-20, 18:39 #4 Mr. P-1     Jun 2003 7·167 Posts 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.
2009-01-20, 19:35   #5
Unregistered

2×3×7×149 Posts

Quote:
 is it possible for the residue of a composite number to be LLR Res64: 0000000000000000 thus making it prime?
Quote:
 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."

Quote:
 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?

 2009-01-20, 20:03 #6 ewmayer ∂2ω=0     Sep 2002 República de California 32·5·11·23 Posts 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.
2009-01-20, 23:13   #7
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

100000101100012 Posts

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

2009-01-20, 23:55   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·17·89 Posts

Quote:
 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
Code:
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?

 2009-01-21, 01:45 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·3·17·89 Posts 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. Last fiddled with by Batalov on 2009-01-21 at 02:14

 Similar Threads Thread Thread Starter Forum Replies Last Post VBCurtis Riesel Prime Search 12 2013-01-24 12:02 flouran Math 34 2009-12-08 00:09 Kosmaj Riesel Prime Search 19 2007-03-28 10:56 MooooMoo Twin Prime Search 23 2007-01-23 17:53 amphoria Riesel Prime Search 74 2006-03-12 11:45

All times are UTC. The time now is 13:40.

Tue Aug 4 13:40:18 UTC 2020 up 18 days, 9:27, 0 users, load averages: 1.90, 2.23, 2.22