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

作者：刘莺迎

来源：科学技术创新, 2020, (36): 109-110.

• 大数分解
• 椭圆曲线方法
• 数域筛法
• CADO-NFS
• 多线程并行

大数分解是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。这些工作对分解算法的理论学习和分解实践具有重要的借鉴意义。

• 单位
  河南牧业经济学院