The Space Complexity Analysis in the General Number Field Sieve Integer Factorization

The General Number Sieve is the most efficient algorithm for integer factorization. It consists of polynomial selection, sieving, solving equations and finding square roots. Root lifting of polynomial is discussed in this paper. The p-adic evaluation provided by each root and the expected p-value are also given. Then we gain the space complexity of sieving and building equations over the ring Z / 2 Z.

Authors

• Qi Wang
• Xiubin Fan
• Hongyan Zang
• Yu Wang

Keywords

• General Number Field Sieve
• Integer factorization
• Mathematical expectation
• p-adic evaluation
• Computational complexity
• Space complexity