Factors

[Safuat Hamdy]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 13 November 2002 20:28, Jaideep Lamba wrote:
> Dear Readers,
>
> I am interested in implementation of various factor finding algorithms.=
 May
> I request to please redirect me to papers / sources where I can find th=
e
> best factor finding algorithm for large numbers and their time complexi=
ty.

<FLAMES>
Your request is actually an impudence.  Searching google would give you=20
probably more answers than asking innocent and busy readers.
</FLAMES>

Having said this, you should go and obtain the following book

R.Crandall, C.Pomerance: Prime Numbers --- A Computational Perspective,=20
Springer Verlag

This book is fairly well written and reveals a lot of internal details of=
=20
various factoring algorithms.  Since you ask your question so naively, I=20
would discourage you strongly from going to real research papers, for thi=
s=20
matter is really not trivial and requires knowledge on algebraic and anal=
ytic=20
number theory in order to get all the details.

As for ready to go implementations, try Paul Zimmermanns ECM-Implementati=
ons=20
(exercise: use google or whatever to find it on the web), my own libiq co=
mes=20
with a Schnorr-Lenstra factorizer, LiDIA contains ECM, p-1, p+1, as well =
as=20
the MPQS (LiDIA's code is not suitable for learning algorithms, though), =
and=20
other readers such as Paul Leyland might give you pointers to NFS=20
implementations.


Best

- --=20

S. Hamdy                                |  All primes are odd except 2,
Dept. of Mathematics & Statistics       |  which is the oddest of all.
University of Calgary                   |
                                        |
unsolicited commercial e-mail           |
is strictly not welcome                 |
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE90z3fwjuT2UdHuKURAk2aAJ9X0D2TjcM1DUE1IHPxxS8AG9tKZgCgi1mB
+iP3cWEI1aKxwOboTKM3yuI=3D
=3D2IJz
-----END PGP SIGNATURE-----