A Parallel GNFS Integrated with the Block Wiedemann´s Algorithm for Integer Factorization

Author

Guo, Na ; Yang, Laurence T. ; Lin, Man ; Quinn, John P.

Author_Institution

Dept. of Comput. Sci., St. Francis Xavier Univ.

fYear

2006

fDate

Sept. 29 2006-Oct. 1 2006

Firstpage

45

Lastpage

50

Abstract

RSA is a very popular public-key based cryptosystem. The security of RSA is relied on the difficulty of large integer factorization. The general number field sieve (GNFS) is an algorithm for factoring very large numbers, especially for integers over 110 digits. It is the asymptotically fastest known factoring algorithm. In this paper, we have successfully implemented the parallel general number field sieve (GNFS) algorithm and integrated with a new method called block Wiedemann´s algorithm to solve the large and sparse linear system over GF(2) generated by the GNFS algorithm. The detailed parallel experimental results on a SUN cluster will be presented as well

Keywords

public key cryptography; RSA; block Wiedemann algorithm; factoring algorithm; general number field sieve algorithm; integer factorization; parallel GNFS algorithm; public-key based cryptosystem; sparse linear system; Clustering algorithms; Computer science; Electronic mail; Galois fields; Internet; Linear systems; Public key; Public key cryptography; Sparse matrices; Sun;

fLanguage

English

Publisher

ieee

Conference_Titel

Dependable, Autonomic and Secure Computing, 2nd IEEE International Symposium on

Conference_Location

Indianapolis, IN

Print_ISBN

0-7695-2539-3

Type

conf

DOI

10.1109/DASC.2006.9

Filename

4030865