Volume 4 Number 2 (Feb. 2009)
Home > Archive > 2009 > Volume 4 Number 2 (Feb. 2009) >
JCP 2009 Vol.4(2): 112-118 ISSN: 1796-203X
doi: 10.4304/jcp.4.2.112-118

A Study on Parallel RSA Factorization

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

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.

General Information

ISSN: 1796-203X
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Sep 13, 2018 News!

    Vol 13, No 10 has been published with online version   [Click]

  • Apr 28, 2019 News!

    Vol 14, No 4 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Mar 20, 2019 News!

    Vol 14, No 3 has been published with online version   [Click]

  • Feb 22, 2019 News!

    Vol 14, No 2 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Jan 04, 2019 News!

    Vol 14, No 1 has been published with online version   [Click]

  • Read more>>