Will Edgington <[EMAIL PROTECTED]> writes:
> 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.
Like the LL algorithm, P-1 and ECM need to store residues as large
as 2^p-1. LL needs only one such residue, P-1 needs a few, ECM needs many.
P-1 and ECM need a GCD (Greatest Common Divisor) routine, which
will need many temporaries if it uses fast algorithms.
Peter Montgomery
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
