Factoring Large Integers Using Parallel Quadratic Sieve by Block Lanczos

摘要

RSA is the most widely used public-key cryptosystem for both encryption and authentication. But it's security relies on the fact that factoring large integer is difficult. So integer factorization becomes a popular studied topic. The Quadratic Sieve (QS) algorithm is the best algorithm for factoring large integer with up to 110 long digits. A parallel QS algorithm has been developed at KTH, Sweden. A critical step in the factoring process of this parallel QS is to solve a linear system formed after sieving using Gaussian Elimination. The complexity of this step is O(n~3) for n by n matrix. Since the matrix formed after sieving is a huge sparse matrix over GF(2), we use Block Lanczos algorithm instead of Gaussian Elimination to solve the linear system. By doing this, we can reduce the complexity to O(n~2), where d is the matrix density which is much smaller than n for sparse matrix. The improvement of the new parallel QS algorithm is also demonstrated by numerical experiments.