四重奏筛保理算法和波拉德 Rho 保理算法的实证比较

当今加密学面临的最重大挑战之一是将大整数计入因子的问题，因为没有算法可以考虑多字形时间，而且对大数进行保理仍然比较困难（200 位数字）。当前加密系统的安全性取决于对大型公钥进行保理的硬度。在这项工作中，我们希望实现两个现有的保理算法 - 波拉德-罗和二次筛 - 并比较其性能。此外，我们想分析两种算法的理论时间复杂性与其实际时间复杂性相比有多近，以及数字的位长度如何影响二筛的性能。最后，我们验证二次筛子在保理小于 80 位的保理数字方面是否比波拉德 - 罗效果更好。

原文题目：An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm

原文：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.