Vector and parallel algorithms for integer factorisation
122. R. P. Brent,
Vector and parallel algorithms for integer factorisation,
Proceedings Third Australian Supercomputer Conference
(Melbourne, December 1990), Strategic Research Foundation,
University of Melbourne, December 1990, 12 pp.
Abstract:
dvi (3K),
pdf (61K),
ps (26K).
Paper:
dvi (23K),
pdf (143K),
ps (71K).
Abstract
The problem of finding the prime factors of large composite numbers is
of practical importance since the advent of public key cryptosystems whose
security depends on the presumed difficulty of this problem.
In recent years the best known integer factorisation algorithms have
improved greatly. It is now routine to factor 60-decimal digit numbers,
and possible to factor numbers of more than 110 decimal digits.
We describe several integer factorisation
algorithms, and consider their suitability for implementation on
vector processors and parallel machines.
Comments
For related work, see
[97,
115,
120].
This paper may be interesting as a summary of the state of integer
factorisation in 1990. There has been much progress since then.
Some more recent surveys are
[ 193,
196].
Go to next publication
Return to Richard Brent's index page