Primality testing and integer factorisation
120. R. P. Brent,
Primality testing and integer factorisation,
in The Role of Mathematics in Science
(Proceedings of a Symposium
held at the Australian Academy of Science, Canberra, 20 April 1990),
Australian Academy of Science, 1991, 14-26.
Abstract:
dvi (3K),
pdf (62K),
ps (26K).
Paper:
dvi (26K),
pdf (158K),
ps (75K).
Transparencies:
pdf (55K),
ps (21K).
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 recent algorithms
for primality testing and factorisation,
give examples of their use, and outline some applications.
Comments
For related work, see
[97,
115,
122].
More recent surveys are
[193,
196].
A talk on 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