>You could build yourself one of those memory expanders that have been designed
>for the TI-92+, and BOOM, instant LL tester. Or even factoring machine. Could
>you factor a Mersenne number without storing it in memory? (Answer: I don't
>*think* so....) Ptoo bad.
Yes, actually you can. By using an algorithm (I think Donald Knuth invented
it, but it *is* in TAOCP vol II). Its not all that complex here is a calc
program to find a^b mod c (which I think explains things better than 2 pages
of mathematical ranting)
define modpow(a,b,c) {
local res;
res=1;
while (b>0) {
if (odd(b)) {
res=a*res;
/* res=res*(a^(2^n)) whenever the nth binary digit of b is 1 everything mod c*/
if (res>c) res=res%c;
}
a=a^2;
if (a>c) a=a%c;
b=(b-odd(b))/2;
}
;
return res;
}
Note that if 2^p==1 mod c then c is a factor. Also note that no number ever
gets bigger than c^2 (keen huh?)
So it is not only possible to find a factor without holding the mersenne number
in memory, but it is considerably faster.
However, I cannot think of any way to do an LL test without storing the
number in memory. Is there way?
-Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
