Factorization of large integers on some vector and parallel computers
156. C. Eldershaw and R. P. Brent,
Factorization of large integers on some vector and parallel computers,
Proceedings of Neural, Parallel and Scientific Computations
1 (1995), 143-148.
Also appeared as TR-CS-95-01, CSL, ANU, January 1995, 6 pp.
A revision appeared as: C. Eldershaw and R. P. Brent,
Integer factorisation on the AP1000,
Proc. Fourth International Parallel
Computing Workshop (PCW'95),
Imperial College, London, 1995, 233-242.
Paper (revised version):
dvi (19K),
pdf (133K),
ps (67K).
Abstract
We compare implementations of two integer factorisation algorithms,
the elliptic curve method (ECM) and a variant of the Pollard "rho" method,
on three machines (the Fujitsu AP1000, VP2200 and VPP500)
with parallel and/or vector architectures.
ECM is scalable and well suited for both vector
and parallel architectures.
Comments
After this paper appeared, Crandall showed that the Pollard "rho" method
is scalable [R. Crandall, Parallelization of Pollard-rho
factorization,
manuscript 1999], although certainly not as easily as ECM.
For a recent survey paper on integer factorisation algorithms,
see [196].
Go to next publication
Return to Richard Brent's index page