Thu, 14 Nov 2002 03:20:49 -0800
> From: Safuat Hamdy [mailto:firstname.lastname@example.org]=20
> On Wednesday 13 November 2002 20:28, Jaideep Lamba wrote:
>> I am interested in implementation of various factor finding=20
>> algorithms. May I request to please redirect me to papers /
>> sources where I can find the best factor finding algorithm
>> for large numbers and their time complexity.
> Having said this, you should go and obtain the following book
> R.Crandall, C.Pomerance: Prime Numbers --- A Computational=20
> Springer Verlag
I also recommend Riesel's book --- full publication details deliberately =
omitted. If you can't be bothered to search amazon.com, you're probably =
not that interested anyway ;-)
> As for ready to go implementations, try Paul Zimmermanns=20
> ECM-Implementations (exercise: use google or whatever to find
> it on the web), my own libiq comes with a Schnorr-Lenstra
Thanks Safuat, I wasn't aware of that resource. I will go chase it.
> LiDIA contains ECM, p-1, p+1, as well as=20
> the MPQS (LiDIA's code is not suitable for learning=20
> algorithms, though), and other readers such as Paul Leyland
> might give you pointers to NFS implementations.
Indeed, and thanks for the opportunity to plug http://www.nfsnet.org. =
Don Leclair, Richard Wackerbarth and I are re-implementing a distributed =
NFS engine. We're still at the beta-test stage so things are *very* =
rough around the edges but we've code that works well enough to complete =
a SNFS factorization of Woodall(668), which is a number with 204 digits, =
and have started 6^257-1.
For personal use (i.e. if you don't want to run a massive distributed =
computation) I found the NFSX packacke for UBASIC quite effective. It's =
really only suitable for SNFS on numbers up to 120 digits, say, and then =
only if you can find an odd-degree poynomial (the sqrt algorithm =
employed doesn't allow even-degree polynomials). Take a look in =
ftp://rkmath.rikkyo.ac.jp./pub/ubtest/ for the distribution.
I apologise for my contribution having essentially nothing to do with =
GMP per se. Nonetheless, I hope that some list members find it useful.