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

作　　者：刘莺迎 

机构地区：[1]河南牧业经济学院信息工程学院,河南郑州450000

出　　处：《科学技术创新》2020年第36期109-110,共2页Scientific and Technological Innovation

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

关 键 词：大数分解 椭圆曲线方法 数域筛法 CADO-NFS 多线程并行 

分 类 号：TN918.4[电子电信—通信与信息系统]