Space Complexity Analysis of Sieving in the Number Field Sieve Integer Factorization

DOI

10.2991/icmmcce-15.2015.70How to use a DOI?

Keywords

number field sieve, integer factorization, mathematical expectation, evaluation, space complexity

Abstract

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 .

Copyright

© 2015, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Qi Wang
AU  - Hongyan Zang
AU  - Xiubin Fan
AU  - Yu Wang
PY  - 2015/12
DA  - 2015/12
TI  - Space Complexity Analysis of Sieving in the Number Field Sieve Integer Factorization
BT  - Proceedings of the 4th International Conference on Mechatronics, Materials, Chemistry and Computer Engineering 2015
PB  - Atlantis Press
SP  - 335
EP  - 340
SN  - 2352-538X
UR  - https://doi.org/10.2991/icmmcce-15.2015.70
DO  - 10.2991/icmmcce-15.2015.70
ID  - Wang2015/12
ER  -