Factorisation of Large Integers on some Vector and Parallel Computers

We compare implementations of two integer factorization algorithms, the elliptic curve method (ECM) and a variant of the Pollard "rho" method, on three machines with parallel and/or vector architectures. ECM is scalable and well suited for both vector and parallel architectures. The "rho" method is simpler than ECM but is not scalable. 1 Introduction The factorization of large integers is a significant mathematical problem with practical applications to public-key cryptography [16]. Although the theoretical complexity of factorization is unknown, it is a computationally expensive task with the best known algorithms. The development of new algorithms and faster machines has made the factorization of "general" integers with 100--120 digits feasible. Several authors have considered vector and parallel implementations of the MPQS and NFS algorithms [5, 8, 10, 14, 15]. These algorithms have the property that the run-time depends mainly on the size of the number N to be factored. For anothe..