Now, I'm going to toss out an idea. I thought about this a few minutes
after reading the previous message and I want to see if you all think its
worthwhile or not, or whether its even correct or not.
Here goes:
1) If we know the last n bits of a number x, then we can (easily) determine
the last n bits of x^2.
2) If we know the last n bits of x^2 we can easily determine the last n bits
of x^2 - 2.
3) It follows by repeating this (I hope) that we can (realatively easily)
determine the last n bits of the last number in the Lucas-Lehmer series.
Now the slightly sketchy part (provided that was all right) . . .
4) There are fewer than, or equal to, 2^n possible combinations of n
terminating bits when we examine the multiples of P = 2^p - 1, i.e. the
group {n_terminating_bits(P), n_terminating_bits(2P),
n_terminating_bits(3P), . . . }. It is my hope that this group has fewer
(ideally significantly fewer) than 2^n elements. That way if the last n
bits of the last term of the Lucas-Lehmer test is a combination of bits
which could not possibly be the final n bits of a product of P, then we know
that the residue cannot be 0.
Layman's example:
any number that ends in ...34587 cannot be divisible by 25. Why? (apart
from the obvious). Because any number that's a multiple of 25 ends in (now
I'm looking at the group {25, 50, 75, 100, 125, 150 . . .}), 00, 25, 50, or
75. ...34587 doesn't end with any of these.
I hope I've explained myself enough that you can either take from this any
worth which it might have, or correct the mistakes I've made. :)
Alex Healy
[EMAIL PROTECTED]
http://www.alexhealy.net
<snip>
> *) Somebody finds a way to verify the output of the LL test
> without a complete rerun (cf. verification of digital
signatures).
> If this eliminates the need for double-checks, does it qualify?
That sounds interesting! Of course, if we could find a _quick_ way of
computing a few bits of the residual, we could use this as a filter
which would remove a large proportion of the contenders - never mind
about being a quick check on a result. I think this really _should_
qualify for an award!
Regards
Brian Beesley
</snip>
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
