Thanks. I was also considering a base other than base 2. But I'm afraid
the same problem arises as long as the base is realatively prime to the
Mersenne number we are considering. For example if you look at 2047 (i.e.
2^11 - 1) in base 23 or base 87 you'll see the algorithm I outline below
actually works, but that that's sort of ad hoc because I know that 23 and 87
are factors. :) Unless someone else has some particularly brilliant
insight, I admit this method is no better than factoring (since we'd need a
base (radix), b such that (b, 2^p - 1) != 1.
Thanks for the feedback,
Alex
Alex,
The group you seek always has 2^n elements. All bit combinations are
possible.
(P = 2^p-1 is "minus one" in n-bit words. 2*P is minus two, etc. up to
2^n*P which is 0. All bit patterns occur.)
Todd Sauke
>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
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
