Mersenne Digest Saturday, June 14 2003 Volume 01 : Number 1074
---------------------------------------------------------------------- Date: Wed, 11 Jun 2003 22:58:49 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: Re: M#40 verification run More bad news to report. I've just gotten a hold of the results.txt file from the original run. There were five SUM(INPUTS) != SUM(OUTPUTS) error during the run. Historically, five errors during a run means there is less than a 50% chance the final LL result will be correct. Now I have to try and figure out what safety checks can be added to prevent false alarms. So far, I have 2 changes planned: 1) Prime95 does not tell the server how many errors occurred for an LL test with a prime result. I'll fix this. Knowing their were 5 errors would have raised red flags earlier on. 2) I'll change prime95 to NOT delete the save files when a new prime is found. When a prime is reported, I'll ask for the save file and rerun the last 30 minutes of the test. I think this would have helped in this case. This measure also deters a hacker. It might be easy for a hacker to spoof a prime report - but he'll have difficulty generating a save file that reports the number as prime after the final 30 minutes of LL testing. There is still a chance this really is prime, we'll know on Friday. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 12 Jun 2003 05:55:31 -0400 From: Nathan Russell <[EMAIL PROTECTED]> Subject: Re: Mersenne: M#40 verification run - --On Wednesday, June 11, 2003 3:15 PM -0400 George Woltman <[EMAIL PROTECTED]> wrote: > Possibilities are: > 1) The original run was flawed or there is a bug in the version of > prime95 used. It is hard to imagine a bug or hardware glitch that > generates an all zero LL result. If memory is zeroed at some point, the > next LL iterations are -2, 2, 2, 2, ... 2) My overclocked machine > generated an undetected error or the prime95 version I'm using has a bug > that is affecting my result. > 3) I was debugging an out-of-memory bug report last night. It is > theoretically possible there is an OS bug that affects other processes in > these severe circumstances. 4) Someone hacked the server. Is this a concern? Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 12 Jun 2003 06:07:36 -0400 From: Nathan Russell <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: M#40 verification run - --On Wednesday, June 11, 2003 10:58 PM -0400 George Woltman <[EMAIL PROTECTED]> wrote: > 2) I'll change prime95 to NOT delete the save files when a new prime is > found. When a prime is reported, I'll ask for the save file and rerun the > last 30 minutes of the test. I think this would have helped in this > case. This measure also deters a hacker. It might be easy for a hacker > to spoof a prime report - but he'll have difficulty generating a save > file that reports the number as prime after the final 30 minutes of LL > testing. That is a collosal understatement. Every modulo operation destroys information, and I'm not sure whether one COULD construct such a file. Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 12 Jun 2003 17:58:56 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: M#40 verification run On Thursday 12 June 2003 10:07, Nathan Russell wrote: > > That is a collosal understatement. Every modulo operation destroys > information, and I'm not sure whether one COULD construct such a file. Indeed. In general there will be more than one x such that x^2-2 = R modulo 2^p-1 so, working backwards through a number of steps, you would have only a very small probability of deriving the same "starting condition". Even if the equation was easy to solve in reverse... Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 12 Jun 2003 17:58:56 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: M#40 verification run On Thursday 12 June 2003 10:07, Nathan Russell wrote: > > That is a collosal understatement. Every modulo operation destroys > information, and I'm not sure whether one COULD construct such a file. Indeed. In general there will be more than one x such that x^2-2 = R modulo 2^p-1 so, working backwards through a number of steps, you would have only a very small probability of deriving the same "starting condition". Even if the equation was easy to solve in reverse... Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 06:45:43 +0200 From: [EMAIL PROTECTED] Subject: Re: Mersenne: Re: M#40 verification run Nathan Russell <[EMAIL PROTECTED]> comments - --On Wednesday, June 11, 2003 10:58 PM -0400 George Woltman <[EMAIL PROTECTED]> wrote: > 2) I'll change prime95 to NOT delete the save files when a new prime is > found. When a prime is reported, I'll ask for the save file and rerun the > last 30 minutes of the test. I think this would have helped in this > case. This measure also deters a hacker. It might be easy for a hacker > to spoof a prime report - but he'll have difficulty generating a save > file that reports the number as prime after the final 30 minutes of LL > testing. That is a collosal understatement. Every modulo operation destroys information, and I'm not sure whether one COULD construct such a file. Nathan Suppose we are able to go back 50 iterations. That is, suppose the checkpoint gives a value x[0] such that if we iterate x[i+1] = x[i]^2 - 2 (mod Mp) for i = 0, 1, ..., 49, then we encounter x[50] = 0. Let q be a prime factor of Mp. Solving the quadratic x[0] = alpha + 1/alpha (mod q) for alpha gives either a solution in GF(q) (with alpha^q = alpha) or a solution in GF(q^2) (with alpha^q = 1/alpha). In both cases x[i] = alpha^(2^i) + alpha^(-2^i) (mod q) for all i. The assumption x[50] = 0 implies alpha^(2^51) = -1 (mod q). The multiplicative order of alpha must be 2^52. But we know this order divides one of q +- 1. Hence q == +- 1 (mod 2^52). This argument applies to all prime factors q of Mp. It seems very unlikely that all prime factors will be +- 1 (mod 2^52) unless Mp is itself prime. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 09:24:18 +0200 From: "Denis Cazor" <[EMAIL PROTECTED]> Subject: Mersenne: Connexion Hello, one of my PCs can't connect to the server and i obtain error 2250. I don't use a firewall and i don't know how i can use HTTP protocol with prime. What can i do ? Thanks for your help Denis Cazor _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 09:41:10 +0200 From: "Denis Cazor" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Connexion Oups ! Sorry, I found it in the FAQ Denis - ----- Message d'origine ----- De : "Denis Cazor" <[EMAIL PROTECTED]> � : "Mersenne, Base" <[EMAIL PROTECTED]> Envoy� : vendredi 13 juin 2003 09:24 Objet : Mersenne: Connexion > Hello, > > one of my PCs can't connect to the server > and i obtain error 2250. I don't use a firewall and > i don't know how i can use HTTP protocol > with prime. > What can i do ? Thanks for your help > > Denis Cazor > _________________________________________________________________________ > Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 15:12:59 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: M#40 verification runs completed Hello all, It is official - not prime. Both Guillermo's Mlucas run and my prime95 run return a matching non-zero residue. We will never know what caused prime95 to generate a false positive, I am studying the code for ways in which a memory corruption could cause this. Something good will come from this sorry ending. I am confidant this incident will have little negative impact on GIMPS. While the episode was probably an unhappy roller-coaster ride for one individual, the false positive problem is far less damaging to GIMPS than the version 17 shift bug disaster. This incident illustrates why most other distributed projects keep any client finds secret (even from the discoverer) until verified. If we had a similar policy this could have been swept under the rug and no one would ever have known. I kind of like our policy though. It lets everyone in on the ups and downs of the project. Thanks to Guillermo and Ernst for dedicating time to the verification run. Best regards, George _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 15:16:24 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: M#40 - what went wrong? It was once thought that a false positive report "couldn't happen". So what went wrong? So far I've come up with two possibilities. 1) The FFT data is zeroed AND does not go into the -2,2,2,2 loop. I don't know how the data gets zeroed, but I've seen it happen. It has happened a lot less often once code was added to reject any save file with all zero data. The not going into the -2,2,2,2 loop can happen with the corruption of a single local variable. I've just added code that makes sure this local variable is always in the range 0 <= variable < exponent. 2) This case results from the way my C compiler treats floating point NaN. NaN stands for not a number. If NaN is converted to an integer, the integer is zero. So if the FFT data is all NaNs, prime95 will report a prime. Prime95 check for NaNs every iteration, but if every FFT data value becomes NaN after the inverse FFT of the last LL iteration, then we get a false positive. Furthermore, corrupting a single value (the initial carry input to rounding and carry propogation code) could set every FFT data value to NaN. I've fixed the code to make sure there are no NaNs in the final is-it-a-prime check. Which of the above is more likely? I don't know. It seems the first requires two or more pieces of memory corrupted, but it leads to a steady state. So the errors can occur at any point during the LL test. The second case requires only one failure, but at a very specific point in time. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 14:00:30 -0700 From: Aaron Lehmann <[EMAIL PROTECTED]> Subject: Re: Mersenne: M#40 - what went wrong? On Fri, Jun 13, 2003 at 03:16:24PM -0400, George Woltman wrote: > 2) This case results from the way my C compiler treats floating point NaN. > NaN stands for not a number. If NaN is converted to an integer, the integer > is zero. So if the FFT data is all NaNs, prime95 will report a prime. I expect this is a FAQ and apologize in advance, but in the age of SSE2 integer instructions why is it still necessary to use floating point calculations? _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 15:42:26 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Re: Mersenne: M#40 - what went wrong? > On Fri, Jun 13, 2003 at 03:16:24PM -0400, George Woltman wrote: > > 2) This case results from the way my C compiler treats floating point NaN. > > NaN stands for not a number. If NaN is converted to an integer, the integer > > is zero. So if the FFT data is all NaNs, prime95 will report a prime. > > I expect this is a FAQ and apologize in advance, but in the age of > SSE2 integer instructions why is it still necessary to use floating > point calculations? precision. The extended FP multiply has 64 bits of mantissa. SSE2 is, I believe, restricted to 32bit multiplies, so it would take 4 times as many to equal one 64bit (gross simplification, but sufficient for the purposes here). _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 19:43:17 -0400 From: "Brandon Gale" <[EMAIL PROTECTED]> Subject: RE: Mersenne: M#40 - what went wrong? > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] Behalf Of John R > Pierce > Sent: Friday, June 13, 2003 6:42 PM > To: Aaron Lehmann; Mersenne discussion list > Subject: Re: Mersenne: M#40 - what went wrong? > > > > On Fri, Jun 13, 2003 at 03:16:24PM -0400, George Woltman wrote: > > > 2) This case results from the way my C compiler treats floating point > NaN. > > > NaN stands for not a number. If NaN is converted to an integer, the > integer > > > is zero. So if the FFT data is all NaNs, prime95 will report a prime. > > > > I expect this is a FAQ and apologize in advance, but in the age of > > SSE2 integer instructions why is it still necessary to use floating > > point calculations? > > precision. > > The extended FP multiply has 64 bits of mantissa. SSE2 is, I believe, > restricted to 32bit multiplies, so it would take 4 times as many to equal > one 64bit (gross simplification, but sufficient for the purposes here). Is that still true on the 64-bit platforms (ia64 and amd64)? Brandon > > > _________________________________________________________________________ > Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > > _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 13 Jun 2003 18:49:26 -0500 From: Mark Rodenkirch <[EMAIL PROTECTED]> Subject: Re: Mersenne: M#40 - what went wrong? Would it be possible for the person who returned this result to run the test again? If their PC indicated that the number is prime again, then George could work with them to track down the problem. - --Mark _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 14 Jun 2003 12:13:54 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Re: Mersenne: M#40 - what went wrong? On Fri, Jun 13, 2003 at 03:42:26PM -0700, John R Pierce wrote: > The extended FP multiply has 64 bits of mantissa. SSE2 is, I believe, > restricted to 32bit multiplies, so it would take 4 times as many to equal > one 64bit (gross simplification, but sufficient for the purposes here). SSE2 can handle 64 bit floating point numbers (not that I can remember off the top of my head how many bits of mantissa there are in those) -- the traditional x86 FPU can handle 80 bits internally, but usually you only save 64 bits of those. In other words, precision is not _that_ big of an issue, even though Prime95 has more conservative limits for SSE2 CPUs. (SSE1, on the other hand, only supports 32 bit numbers, and thus is not usable for Prime95.) The biggest problem with SSE2 is of course that it's only supported on the Pentium 4 yet -- they are becoming increasingly common, but for instance, no current AMD chip supports it. /* Steinar */ - -- Homepage: http://www.sesse.net/ _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #1074 *******************************
