I think most of this has been covered before, but a few comments may
be in order.
1) There are other residual values worth checking for as well as 0.
In fact detection of any closed loop is useful information because it
enables us to "write down" the residual at _any_ subsequent iteration
without the bother of actually doing the calculation.
2) You do _not_ need to store the whole residual every time. If you
store only the bottom 64 bits you will get about one spurious match
every 2^64 iterations ... but we're doing far fewer than that number
of iterations. Only on the rare occasions when we do get a match is
it worth looking at the whole residual; the best method of doing this
(given that we now know where the cycle starts, so we need to keep
only that value) is to repeat the calculation from the start, or
nearest previous checkpoint file, if one is available.
(InterimFiles!)
3) Since the Lucas-Lehmer algorithm is a suitable function, if we
_do_ happen to detect a looping value of the residual, a proper
factor can be extracted by Pollard's rho method.
4) Existence of a residual loop within the first p-2 iterations is
most unlikely. If we want to use Pollard's rho method to find factors
of 2^p-1, we would be much better advised to use a formula of the
type x(n+1) = (x(n))^(4*p)+a rather than the Lucas sequence; since
this type of formula selects for factors of type 2kp+1, the extra
work per iteration would be worthwhile.
5) Note that, statistically, there are "about" 2 values x such that
x^2-2 = a (mod 2^p-1) for an arbitary a. In general, then we would
"expect" to have to execute "about" p iterations before hitting a
recurrence, rather than the maximum possible cycle length of 2^p-1.
This statement seems to be opposed to the point above, I don't know
the reason! (Probably something to do with a large number of values
(a+2) which are quadratic non-residues modulo 2^p-1 ?)
6) Another possible line of approach related to the suggestion is as
follows.
Does there exist an x such that x^2 - 2 = 0 (mod 2^p -1), i.e. is 2 a
quadratic residue residue modulo 2^p-1? If not, then the (p-2)th term
in the L-L sequence cannot possibly be zero, so there's no point in
executing the L-L test.
Unfortunately, since 2^p-1 = -1 (mod 8) for all odd primes p, it
follows that 2 is a quadratic residue modulo 2^p-1 for all odd
primes p. Hence the observation is useless.
Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
