WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 24, 2025
Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
Authors: , ,
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 $$d_i$$ to the $$md_i$$ (m is a small integer), which can change the complexity from $$O(n)$$ to $$O( \frac{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.
Search Articles
Keywords: integer factorization, quadratic sieve, parameter lookup tables, factor base, algorithm optimization, prime numbers, large integers
Pages: 86-91
DOI: 10.37394/23205.2025.24.8