Recent progress and prospects for integer factorisation algorithms
196. R. P. Brent,
Recent progress and prospects for integer factorisation algorithms
(invited talk),
Proc. COCOON 2000
(Sydney, July 2000),
Lecture Notes in Computer Science, Volume 1858,
Springer-Verlag, Berlin, 2000, 3-22.
MR 2002h:11138.
Also (preliminary version): Report PRG-TR-03-00, 26 April 2000.
Preprint:
dvi (33K),
ps (89K).
Paper:
pdf (272K)
Report:
ps (112K).
Abstract
The integer factorisation and discrete logarithm problems are
of practical importance because of the widespread use of
public key cryptosystems whose
security depends on the presumed difficulty of solving these problems.
This paper considers primarily the integer factorisation problem.
In recent years the limits of the best integer factorisation algorithms have
been extended greatly, due in part to Moore's law and in part to
algorithmic improvements.
It is now routine to factor 100-decimal digit numbers,
and feasible to factor numbers of 155 decimal digits (512 bits).
We outline several integer factorisation
algorithms, consider their suitability for implementation on
parallel machines, and give examples of their current capabilities.
In particular, we consider the problem of parallel solution of the
large, sparse linear systems which arise with the MPQS and NFS methods.
Comments
This is mainly a review paper, but Section 7 on parallel solution of
large, sparse linear systems by the Lanczos method is new.
Other papers on
integer factorisation include:
-
Brent and Pollard
[61] on the factorization of
F8
-
Brent
[102] on the
elliptic curve method
-
Brent
[113,
115] on the factorization of F11
-
Eldershaw and Brent
[156] on parallel implementations of
the ECM and Pollard rho methods
-
Brent
[161] on the factorization of
F10
-
Brent, Crandall, Dilcher and Van Halewyn
[175] on some new factors of
F13,
F15 and F16
- Murphy and Brent
[178]
on polynomial selection in NFS,
relevant to the factorisation of
RSA155
-
Brent
[122, 193] for
other surveys
- A talk on the related topic of
Primality Testing
(including comments on the AKS deterministic polynomial-time algorithm)
is available here.
Go to next publication
Return to Richard Brent's index page