Abstract: dvi (3K), pdf (75K), ps (29K).
Paper: dvi (22K), pdf (134K), ps (66K).
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 F11 = 2211 + 1 which was accomplished using ECM.
Go to next publication
Return to Richard Brent's index page