摘要
数域筛法(NFS)是目前大数分解效果最好的算法,它的研究对于当前的公钥密码体系有着重要的意义。对数域筛法进行了综述,尤其是多项式选择、数对筛选、矩阵生成、矩阵求解、平方根求解和大整数运算等关键步骤,同时介绍了数域筛法中五个步骤计算量的示例、RSA-240最新的多项式和多项式选择对数对筛选效率的影响,指出低复杂度算法、与体系结构相适应的算法、海量大整数协同分解、高效的数对筛选和高效大整数运算等技术是未来值得关注的方向。
Number Field Sieve （NFS） is the best algorithm for large integer factorization, and its research has important significance for public key cryptography. The NFS, especially the key steps such as polynomial selection, sieving, matrix generation, matrix solution, square root solution and large integer arithmetic were summarized. Examples of the computational cost of the five steps in NFS, the effect of the latest polynomials of the RSA-240 and the impact of the polynomial selection on the sieving efficiency were given. It is pointed out that low complexity algorithms, the algorithms adapting to computer architecture, the cooperative factorization methods for a large number of large integers, efficient sieving technology and efficient large integer arithmetic deserve our attention in the future.
作者
李翊谁
穆雨桐
迟利华
刘杰
孙扬
包为民
龚春叶
LI Yishui;MU Yutong;CHI Lihua;LIU Jie;SUN Yang;BAO Weimin;GONG Chunye(Laboratory for Parallel ＆ Distributed Processing,National University of Defense Technology,Changsha Hunan 410073,China;High-tech Research Institute,Hunan lastitute of Traffic Engineering,Xiangyin Hunan 414600,China;72465 Unit of the PLA,Jinan Shandong 250022,China;China Aerospace Science and Technology Corporation,Beijing 100048,China)
出处
《计算机应用》
CSCD
北大核心
2018年第A01期104-107,共4页
journal of Computer Applications
基金
国家重点研发计划项目(2017YFB0202104)
国家自然科学基金资助项目(61402039
91430218
91530324
71601182)
博士后基金资助项目(2014M562570
2015T81127)
核反应堆系统设计技术重点实验室基金资助项目(SQ-KFKT-02-2016004)
关键词
数域筛法
信息安全
多项式选择
数对筛选
RSA公钥加密算法
大整数分解
Number Field Sieve （NFS）
information security
polynomial selection
sieve
RSA algorithm
large integer factorization
