JOURNAL OF COMPUTERS (JCP)

ISSN : 1796-203X

Volume : 4 Issue : 2 Date : February 2009

**A Study on Parallel RSA Factorization**

Yi-Shiung Yeh, Ting-Yu Huang, Han-Yu Lin, and Yu-Hao Chang

Page(s): 112-118

Full Text: PDF (141 KB)

**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

ISSN : 1796-203X

Volume : 4 Issue : 2 Date : February 2009

Page(s): 112-118

Full Text: PDF (141 KB)

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.