Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435243 | Theoretical Computer Science | 2016 | 19 Pages |
Abstract
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/2ZZ/2Z.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Qi Wang, Xiubin Fan, Hongyan Zang, Yu Wang,