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