Some parallel algorithms for integer factorisation (Q4945780)

This paper surveys all the current methods used to factor numbers. It starts with a discussion of the relevant machine arithmetic and then goes on to discuss methods such as Pollard's rho and \(p-1\) method. Then the author discusses Lenstra's elliptic curve method (ECM), which is based on the \(p-1\) method. Various aspects of ECM are discussed including the implementation on a parallel machine and the second phase of the ECM algorithm. Finally the author discusses the three main modern sieve based algorithms, namely the multi-polynomial quadratic sieve (MPQS), the special number field sieve (SNFS) and the general number field sieve (GNFS). A report on the factoization of RSA-140 is given and it is stated that the factorization of RSA-155 is being carried out (a program which has now been completed). For the entire collection see [Zbl 0921.00036].