<<Uh, that's exactly what Prime95 does. To test whether a potential factor f
divides 2^p-1, we use a standard binary powering algorithm to compute 2^p
modulo f; it requires roughly log2(p) operations on numbers no bigger than
f, and we never have to store the full representation of 2^p-1. I'm sure
that this could be done on a TI. I don't know about ECM though.>>
So, is this:
(2^p mod f) - 1
Congruent to this:
(2^p -1) mod f
I believe so. If that's true, whoo hoo! I have code to do this already. And
it's relatively speedy. (It makes up the core of my RSA key generation and
encryption machine, which of course is heavy on exponentiation modulo some
other number).
This is doubly great, because TI-92s can go up to 614 decimal digit
precision, so I can store the entire factor.
<<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)>>
I am completely and utterly C illiterate. Mathematical ranting makes more
sense. BASIC is also good. But it doesn't matter, because I have a TI-92
function already that does a^b mod c.
<<Note that if 2^p==1 mod c then c is a factor.>>
If this is correct, I will craft a TI-92 program immediately to factor
Mersenne numbers. *drool drool* An untapped source of computing power exists.
Even if we can't factor up to 2^62 like larger computers can, TI users will
be able to scan low factors. Not sure how fast, though. Yippee!
<<However, I cannot think of any way to do an LL test without storing the
number in memory. Is there way?>>
Neither can I. And TIs don't have 4MB RAM. *sob*.
S.T.L.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
