A Parallel GNFS Integrated with the Block Wiedemann's Algorithm for Integer Factorization
Na Guo, Laurence Tianruo Yang, Man Lin, John F. Quinn · 2006
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