An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm
This work addresses the challenge of factoring large integers, which is crucial for cryptography security, but it is incremental as it compares existing methods without introducing new algorithms.
The paper tackled the problem of factoring large integers by empirically comparing the Quadratic Sieve and Pollard Rho algorithms, finding that the Quadratic Sieve performs better for numbers smaller than 80 bits.
One of the most significant challenges on cryptography today is the problem of factoring large integers since there are no algorithms that can factor in polynomial time, and factoring large numbers more than some limits(200 digits) remain difficult. The security of the current cryptosystems depends on the hardness of factoring large public keys. In this work, we want to implement two existing factoring algorithms - pollard-rho and quadratic sieve - and compare their performance. In addition, we want to analyze how close is the theoretical time complexity of both algorithms compared to their actual time complexity and how bit length of numbers can affect quadratic sieve's performance. Finally, we verify whether the quadratic sieve would do better than pollard-rho for factoring numbers smaller than 80 bits.