On 19 Jul 99, at 18:40, Todd Sauke wrote:
> 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
In general, what you say is true - but try computing the LL sequence
to one hexit precision (i.e. working to base 16). Starting from 4, we
get 0x0E, then 2 ; since 2*2-2 = 2, _all_ the subsequent values are
2, so we can compute the low order 4 bits of the umpteen zillionth
term of the LL sequence as fast as we can load the value 2 into a
register!
Oops - doesn't work - forgot to take the modulus - otherwise there
could be _no_ Mersenne primes except 7 = 2^3-1 ;-)
It's taking the modulus which is the key to the whole LL test, and
what the problem essentially boils down to is _any_ way of computing
the remainder of a division whilst working to a lower precision than
the number of bits in the divisor.
Now I wouldn't say that this is completely impossible, but the very
idea seems about as counter-intuitive as the notion of having several
networked processors cooperating on an FFT without being able to
share data at memory bus speed and without being significantly
delayed by waiting for each other's intermediate results to become
available.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
