Programming Research Group
Technical Report TR-3-00
Recent progress and prospects for integer factorisation algorithms
Richard P. Brent
April 2000, 17pp.
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.
This paper is available as a 104556 gzipped PostScript file.