20090120, 05:37  #1 
12401_{8} 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, 0F), but it is possible, right? 
20090120, 11:46  #2  
Aug 2002
Ann Arbor, MI
661_{8} Posts 
Quote:
The theorem that the LLtest 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 nonzero 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. 

20090120, 16:10  #3 
"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. 
20090120, 18:39  #4 
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.

20090120, 19:35  #5  
2,129 Posts 
Quote:
Quote:
"Number N is composite, but the last few digits of the (nonzero) residue are 0000000000000000. Therefore, the program thinks that it's prime, but it's really composite." Quote:


20090120, 20:03  #6 
∂^{2}ω=0
Sep 2002
República de California
26472_{8} Posts 
I can't speak for George's Prime95 code, but the typical endoftest 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 64bit 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 newprime verification process would quickly reveal the notprimebutRes64zero 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 residuebased checksums such as the SelfridgeHurwitz residues computed as part of Fermat number testing, where we also compute the residue modulo 2^351 and 2^361. Those would reduce the odds of such a "false positive" by additional multiplicative factors of roughly 1/2^35 and 1/2^36, respectively. 
20090120, 23:13  #7  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2^{3}×31×37 Posts 
Quote:


20090120, 23:55  #8  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,257 Posts 
Quote:
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 nonzero 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 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? 

20090121, 01:45  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,257 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 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 20090121 at 02:14 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
About two false primes  VBCurtis  Riesel Prime Search  12  20130124 12:02 
R.H. May be False? wtf  flouran  Math  34  20091208 00:09 
False primes  Kosmaj  Riesel Prime Search  19  20070328 10:56 
False primes!  MooooMoo  Twin Prime Search  23  20070123 17:53 
Four False Primes  amphoria  Riesel Prime Search  74  20060312 11:45 