Space Complexity Analysis of Sieving in the Number Field Sieve Integer Factorization
Qi Wang, Hongyan Zang, Xiubin Fan, Yu Wang · 2015
The general number sieve is the most efficient algorithm known integer factorization, it consists of polynomial selection, sieving, solving equations and finding square roots. In this paper, the evaluation provided by each root and the expected value are given, then we get the space complexity of sieving over the ring .