lrwiman writes:
However, I cannot think of any way to do an LL test without storing
the number in memory. Is there way?
Yes. All of the GIMPS programs do the LL test without the Mersenne
number itself.
The LL test programs do, however, need to store numbers as large as
the Mersenne number itself, which factorers do not need to do.
I would guess that the "trick" you are missing is that the Mersenne
number itself is not needed to do the mod by it:
(a*2^n + b) (mod 2^n - 1) = (a*(2^n - 1) + a + b) (mod 2^n - 1)
= (a*0 a + b) (mod 2^n - 1)
That is, if you have a number that is larger than 2^n, split it every
n bits, shift all the "pieces" down into the 0 thru (n - 1) bits, add,
and repeat while the sum is larger than 2^n - 1 (i.e., occupies more
than the lowest n bits).
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
