## Integer Factorization

150. R. P. Brent, Integer Factorization,
in * Grand Challenges in Supercomputing at the Australian National
University* (edited by T. Bossomaier, D. Singleton and M. Kahn),
CSL, ANU, April 1994, 34-39.
Paper:
dvi (7K),
pdf (104K),
ps (42K).

## Abstract

The problem of finding the prime factors of large composite numbers has
always been of mathematical interest. With the advent of
public key cryptosystems
it is also of practical importance, because the security of
some of these cryptosystems,
such as the Rivest-Shamir-Adleman (RSA) system,
depends on the difficulty of factoring the public keys.
In recent years the best known integer factorization algorithms have
improved greatly, to the point where it is now easy to factor a
60-decimal digit number, and possible to
factor numbers larger than 120 decimal digits,
given the availability of enough computing power.
However, the problem of integer factorization still appears
difficult, both in a practical sense (for numbers of more than
about 80 decimal digits), and in a theoretical sense
(because none of the algorithms run in polynomial time).

We outline several recent integer factorization algorithms,
including the elliptic curve algorithm (ECM),
the multiple polynomial quadratic sieve (MPQS),
and the special/general number field sieve (NFS),
give examples of their use, and mention some applications.

Go to next publication

Return to Richard Brent's index page