# Factors

**Paul Leyland
**
pleyland@microsoft.com

*Thu, 14 Nov 2002 03:20:49 -0800*

>* From: Safuat Hamdy [mailto:hamdy@math.ucalgary.ca]=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
*>*=20
*>* R.Crandall, C.Pomerance: Prime Numbers --- A Computational=20
*>* Perspective,=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
*>* factorizer,
*
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.
Paul