Foghorn Leghorn writes:
>Could you factor a Mersenne number without storing it in memory?
>(Answer: I don't *think* so....) Ptoo bad. If we could factor
>Mersenne numbers on an unmodified TI-92+, then there'd be a lot of
>people who'd run that program.
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.
I'm not sure about ECM either, but P-1 can be done using this same
algorithm to do most of it's work. And I _think_ ECM can use this as
well, just not for the entire job.
See merspm1.c of the mers package for a very simple (and slow)
implementation of P-1. There is a faster one out there, based on
George Woltman's FFT code from prime95, called Factor98.
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
