## Parallel algorithms for integer factorisation

115. R. P. Brent,
Parallel algorithms for integer factorisation,
* Number Theory and Cryptography*
(edited by J. H. Loxton),
London Mathematical Society Lecture Note Series 154,
Cambridge University Press, 1990, 26-37.
MR 91h:11148, 90m:11003.
Abstract:
dvi (3K),
pdf (75K),
ps (29K).

Paper:
dvi (22K),
pdf (134K),
ps (66K).

## 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 factorisation 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.

We describe several algorithms, including the
*elliptic curve method* (ECM), and the
*multiple-polynomial quadratic sieve* (MPQS) algorithm,
and discuss their parallel implementation.
It turns out that some of the algorithms are very well suited
to parallel implementation. Doubling the degree of parallelism
(i.e. the amount of hardware devoted to the problem) roughly
increases the size of a number which can be factored in a fixed
time by 3 decimal digits.

Some recent computational results are mentioned, for example,
the complete factorisation of the 617-decimal digit Fermat number
F_{11} = 2^{211} + 1
which was accomplished using ECM.

## Comments

The factorisation of F_{11} was announced
here and in [113]. For more details of
the computation see [161].
Go to next publication

Return to Richard Brent's index page