大整数分解算法的设计与实现

摘要

大数分解是RSA公钥密钥最直接的攻击手段,对其研究具有极其重要理论价值和现实意义.本文对大整数分解基本原理、方法和软件工具进行了系统梳理,分别利用Pollard rho算法、P-1算法、椭圆曲线分解算法、数域筛法,结合Magma、Yafu、GMP-ECM和Cado-nfs等工具和开源软件实现了RSA-155和1434比特大数分解.在并行优化方面,在Intel Xeon E5-2620 v4@2.1GHz,16cores的服务器中使用Cado-nfs以多线程并行方式对383比特整数进行加速分解,用时约2.4小时,加速比约为9.2.这些工作对分解算法的理论学习和分解实践具有重要的借鉴意义.