Some parallel algorithms for integer factorisation
193. R. P. Brent,
Some parallel algorithms for integer factorisation (invited paper),
Proc. Fifth International Euro-Par Conference
(Toulouse, France, 1-3 Sept 1999),
Lecture Notes in Computer Science, Volume 1685,
Springer-Verlag, Berlin, 1999, 1-22.
Paper (original version):
dvi (37K),
pdf (397K),
ps (97K).
Paper (extended and updated version):
dvi (42K),
pdf (318K),
ps (107K).
Transparencies:
dvi (1 per page, 22K),
pdf (4 per page, 189K),
ps (4 per page, 128K).
Abstract
Algorithms for finding the prime factors of large composite numbers are
of practical importance because of the widespread use of
public key cryptosystems whose
security depends on the presumed difficulty of the 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 describe several integer factorisation
algorithms, consider their suitability for implementation on
parallel machines, and give examples of their current capabilities.
Comments
The transparencies are from an invited talk at Euro-Par '99.
The original version of the paper was written before the factorisation
of the 512-bit number RSA155 was completed. This impressive factorisation
was announced shortly before Euro-Par '99 and is incorporated
in the "extended and updated" version of the paper.
The paper Murphy and Brent
[178]
is relevant to the factorisation of
RSA155.
Other papers on
integer factorisation include:
-
Brent and Pollard
[61] on the factorization of
F8
-
Brent
[102] on the
elliptic curve method
-
Brent
[113,
115] on the factorization of F11
-
Brent
[161] on the factorization of
F10
-
Brent, Crandall, Dilcher and Van Halewyn
[175] on some new factors of
F13,
F15 and F16
-
Brent
[196] for a more recent survey
Go to next publication
Return to Richard Brent's index page