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

Upgrade factorization of integers and impact on RSA cryptosystem

作　　者：姚金江[1] 武传坤[2] 

机构地区：[1]山东临沂师范学院理学院,山东临沂276005 [2]中国科学院软件研究所,北京100190

出　　处：《计算机工程与应用》2011年第20期91-95,共5页Computer Engineering and Applications

基　　金：国家重点基础研究发展规划(973)(No.2007CB807902)~~

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

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

分 类 号：TP309[自动化与计算机技术—计算机系统结构]