Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan, Republic of China

Abstract—The RSA cryptosystem is one of the widely used public key systems. The security of it is based on the intractability of factoring a large composite integer into two component primes, which is referred to as the RSA assumption. So far, the Quadratic Sieve (QS) is the fastest and general-purpose method for factoring composite numbers having less than about 110 digits. In this paper, we present our study on a variant of the QS, i.e., the Multiple Polynomial Quadratic Sieve (MPQS) for simulating the parallel RSA factorization. The parameters of our enhanced methods (such as the size of the factor base and the length of the sieving interval) are benefit to reduce the overall running time and the computation complexity is actually lower. The experimental result shows that it only takes 6.6 days for factoring larger numbers of 100 digits using the enhanced MPQS by 32 workstations.

Index Terms—RSA, factorization, cryptosystem, Multiple Polynomial Quadratic Sieve.

[PDF]

Cite: Yi-Shiung Yeh, Ting-Yu Huang, Han-Yu Lin and Yu-Hao Chang, "A Study on Parallel RSA Factorization," Journal of Computers vol. 4, no. 2, pp. 112-118, 2009.