PreprintCC BY 4.0arXiv
Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
Abstract
The quadratic sieve method is a core tool in number theory. In this paper, we present two optimization methods for the Quadratic Sieve algorithm. In the sieving process, the original polynomial root value accumulation step is changed from the original di to the mdi (m is a small integer), which can change the complexity from O(n) to O(n/m). Another optimization method is that for all parameter lookup steps, the original traversal lookup can be changed to an efficient binary search, which can change the complexity of the loop from O(n) to O(logn). This enhancement reduces the computational complexity of RSA modulus factorization in practical settings.
Versions
Related
- Improved deterministic integer factorization by quadratic-image sieving
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
- Global Optimization of Mixed-Integer Bound-Constrained Quadratic Fractional Problems
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
BibTeX
@misc{guan2026optimization,
title = {{Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization}},
author = {Zihan Guan and Xiaodong Zhuang and Nikos E. Mastorakis},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06576},
eprint = {2609.06576},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06576},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
AU - Zihan Guan
AU - Xiaodong Zhuang
AU - Nikos E. Mastorakis
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06576
UR - https://arxiv.org/abs/2609.06576
AB - The quadratic sieve method is a core tool in number theory. In this paper, we present two optimization methods for the Quadratic Sieve algorithm. In the sieving process, the original polynomial root value accumulation step is changed from the original di to the mdi (m is a small integer), which can change the complexity from O(n) to O(n/m). Another optimization method is that for all parameter lookup steps, the original traversal lookup can be changed to an efficient binary search, which can change the complexity of the loop from O(n) to O(logn). This enhancement reduces the computational complexity of RSA modulus factorization in practical settings.
ER -