Factors

[Paul Leyland]

> 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