> Are you aware of anyone who has implemented an efficient version of
such a method? It would be nice to have some idea of its speed in
practice before spending the significant programming time it would
need to code a (say) Mersenne-optimized version of it for various
hardware targets.
No, I don't know of anyone who's implemented this.
I think Bill Gosper implemented the version with a one word target.
He's also an expert on fast GCD, although that's less important for
the problem at hand.
Dan Bernstein, and I think Dan Coppersmith, have considered related
problems. Bernstein may have done some implementation work.
On the other hand, since the proposal will require a fair number of
multiplies modulo Mp = 2^p-1, with p = ~10,000,000, there are other
possibilities to consider. Since Lucas testing an Mp takes ~10M
big multiplies, it makes sense to ask if say, 1M big multiplies
would find a significant fraction of (relatively) small factors.
1M big multiplies would go a long way in either Pollard Rho or
elliptic curve factoring. We might ask our friends doing ECM
factoring if they can cook up elliptic curves that are more
likely than average to have orders divisible by 2kP+1, or 8k+-1.
Rich Schroeppel [EMAIL PROTECTED]
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
