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
