整数分解的升级算法及对RSA密码体制的影响

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (20): 91-95.

整数分解的升级算法及对RSA密码体制的影响

姚金江1，武传坤2

1.山东临沂师范学院理学院，山东临沂 276005
2.中国科学院软件研究所，北京 100190

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-11 发布日期:2011-07-11

Upgrade factorization of integers and impact on RSA cryptosystem

YAO Jinjiang1，WU Chuankun2

1.School of Sciences，Linyi Normal University，Linyi，Shandong 276005，China
2.Institute of Software，Chinese Academy of Sciences，Beijing 100190，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-11 Published:2011-07-11

摘要/Abstract

摘要： 对Pollard的(p-1)-整数分解算法进行了修改，使其在提高了运行速度的同时，也适用于一些不满足原始(p-1)-整数分解算法的局限条件的数;在(p-1)-分解算法基础上，进一步提出了一种高阶升级分解算法;并给出了在对抗整数分解方面，素数好坏的一种度量方法，在这种新度量方法下，提出了素数稳定阶数的概念，从而说明满足Rivest 条件的数仅仅在对抗二级升级算法时是安全的。

关键词: 整数分解, (p-1)-算法, RSA 密码体制

Abstract: This paper gives a generalization of Pollard’s [(p-1)]-factorization method so that the generalized algorithm not only works more efficiently，but also works on some integers on which the original Pollard’s [(p-1)]-factorization algorithm does not work;based on the [(p-1)]-factorization method，it proposes a higher order upgrade factorization algorithm.This paper further proposes a measure on the robustness of prime numbers in terms of resisting factorization.Under this new measure，this paper proposes the concept of stability order of prime numbers，which means that those numbers satisfying Rivest’s condition are robust only against the second order upgrade factorization.

Key words: integer factorization, the (p-1)-method, RSA cryptography

姚金江1，武传坤2. 整数分解的升级算法及对RSA密码体制的影响[J]. 计算机工程与应用, 2011, 47(20): 91-95.

YAO Jinjiang1，WU Chuankun2. Upgrade factorization of integers and impact on RSA cryptosystem[J]. Computer Engineering and Applications, 2011, 47(20): 91-95.

[1]	荣维坚1，郭亚峰2，黄振杰2. 整数分解问题下的基于证书数字签名方案[J]. 计算机工程与应用, 2014, 50(11): 75-80.
[2]	薛荣红，张建中. 对二次剩余构造的签名方案的分析与改进[J]. 计算机工程与应用, 2011, 47(22): 102-104.
[3]	白凤伟，闫德勤，张鑫彦，郑宏亮. 二次剩余下改进He-Dawson的多秘密共享方案[J]. 计算机工程与应用, 2011, 47(13): 113-115.