Integer factorization for RSA cryptosystem under a PVM environment

摘要

The security of some of these cryptosystems such as the Rivest-Shamir-Adelman (RSA) cryptosystem depends on the difficulty of integer factorization problem. In recent years, with the computation capability brought by modern cluster computing technique, the integer factorization has become much easier than before. We here use the cluster computing technique and fast integer factorization algorithms to show the computation power and factorization capability. This paper will incorporate the Miller-Rabin primality test method and several famous factorization algorithms, including the Pollard p-1 method, elliptic curve method (ECM), and multiple polynomial quadratic sieve (MPQS) algorithms in the parallel virtual machine (PVM) environment. Based on the experimental results, we can find out we can improve integer factorization performance by using modern cluster computing technique, moreover, as some of the algorithms are very well operated and suited to parallel computing environment, our integer factorization implementation achieves additional performance improvement. We believe that the PC cluster computing technology has ushered in low-cost commodity supercomputing as a new parallel computing era, supercomputer is no longer the only solution to solve complex problems in the future.