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:

Go to next publication

Return to Richard Brent's index page