mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-01-20, 05:37   #1
Unregistered
 

161016 Posts
Default 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?
  Reply With Quote
Old 2009-01-20, 11:46   #2
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

1B116 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.
Kevin is offline   Reply With Quote
Old 2009-01-20, 16:10   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

My guess is that the full residue is checked when the
last 16 hexdigits are found to be 0.
davieddy is offline   Reply With Quote
Old 2009-01-20, 18:39   #4
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

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.
Mr. P-1 is offline   Reply With Quote
Old 2009-01-20, 19:35   #5
Unregistered
 

2×3×7×149 Posts
Default

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 View Post
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?
  Reply With Quote
Old 2009-01-20, 20:03   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

32·5·11·23 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2009-01-20, 23:13   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100000101100012 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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).
Uncwilly is online now   Reply With Quote
Old 2009-01-20, 23:55   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·17·89 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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?
Batalov is offline   Reply With Quote
Old 2009-01-21, 01:45   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·17·89 Posts
Default

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
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
About two false primes VBCurtis Riesel Prime Search 12 2013-01-24 12:02
R.H. May be False? wtf flouran Math 34 2009-12-08 00:09
False primes Kosmaj Riesel Prime Search 19 2007-03-28 10:56
False primes! MooooMoo Twin Prime Search 23 2007-01-23 17:53
Four False Primes 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.