整数质因子分解算法新进展与传统密码学面临的挑战

摘要

大整数的质因子分解研究是现代数论领域的一个重要课题,其中涉及很多开问题.随着信息时代的来临,大整数质因子分解的复杂性更成为现代密码学的重要理论基础.著名的RSA公钥密码系统的安全性即建立在解决此问题的困难性之上.本文系统地综述了现代理论计算机科学研究中提出的几种解决该问题的新算法,并介绍了量子计算机高效解决此问题的原理和实现方式.最后,本文讨论了在未来量子计算时代传统密码学所面临的挑战并展望了量子密码学的前景.