Title :
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.
fDate :
Sept. 29 2006-Oct. 1 2006
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;
Conference_Titel :
Dependable, Autonomic and Secure Computing, 2nd IEEE International Symposium on
Conference_Location :
Indianapolis, IN
Print_ISBN :
0-7695-2539-3
DOI :
10.1109/DASC.2006.9
