Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization

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 𝑑𝑖 to the 𝑚𝑑𝑖 (m is a small integer), which can change the complexity from 𝑂(𝑛) to 𝑂 ( 𝑛 𝑚 ). 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 𝑂(𝑛) to 𝑂(𝑙𝑜𝑔𝑛) . This enhancement reduces the computational complexity of RSA modulus factorization in practical settings.