RSA算法中快速生成大素数方法的改进

《RSA算法中快速生成大素数方法的改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据2009年6月第28卷第3期重庆文理学院学报(自然科学版)JournalofChongqingUniversityofArtsandSciences(NaturalScienceEdition)JurL，2009VoL28No．3RSA算法中快速生成大素数方法的改进王萍1，廖芳燕1，廖芳午1，张树贵2(1．成都理工大学信息管理学院，四川成都610059；2．成都理工大学环境与土木工程学院。四川成都610059)[摘要]根据同余理论提出一种快速试除法来更快地判断一个大整数是否能被小素数整除，从而进一步提高RSA算法中所需要的大素数的生成速度．[关键词]RSA；大素数；

2、同余[中图分类号]0156．1[文献标识码]A[文章编号]1673—8012(2009)03—0009—031RSA算法简介RSA算法是一种既能用于加密又能用于数字签名的公钥算法⋯．其原理是：选取两个大素数P和q，算出n=P·q，咖(n)=(p一1)·(q—1)，再随机选取一个正整数e，使之满足1

3、度旧J．目前，因子分解速度最快的方法，其时间复杂度为：exp(sqrt(In(／'t)lnln(n)))．随着n长度的增加，分解因子所需时间成指数增加．现在．129位十进制数的模数是能分解的临界数．因此，n应该大于这个数．可见，RSA的安全性取决于大整数的长度．2生成大素数的方法由于素数在正整数序列中分布不规则，无法用公式直接计算出一个指定长度的大素数，所以当前采用的方法是随机产生一个大整数，再对其做素性检测．常见的素性检测法有Miller—Rabin检测”1、Solovay—Strassen检测法和Lehman检测法．目前，提高素数生成速度的方法是用100以内的小素数首先

4、进行筛选”。．这是因为判断大整数能否被小素数整除的时间要比各种概率测试法短得多，一般说来，这种筛选可以排除大整数不是素数76％的可能性；之后再进行5次Miller—Rabin检测，那么这个大数不是素数的概率就会降到1／1000以下，这样就加快了大素数生成的速度．3对传统筛选法的改进以上提到的用小素数试除法是一种有效的排除合数的方法．那么怎样可以更快地判断一个随机大整数是否能被100以内的小素数除尽呢?根据同余的理论，我们可以将大整数“分块”相加再除以小素数，若能除尽则该大整数肯定能被除尽．3．1快速试除法我们知道，判定一个整数能否被3整除，可以把每一位上的数字相加再除以3，

5、如果能除尽则该数能被3整除，这比直接用这个数去除3要快得多．其原理是：10兰1(mod3)，因此10‘兰1(mod3)∞1．任意一个十进制的整数(aka¨⋯o,1ao)10可表示如下：(akaI一1⋯(21ao)10=at。102+aI—l·10‘一1+⋯+a1·10+ao基a^+a^一l+⋯+a1+ao(mod3)．因此，只要把大整数各位上的数字加起来模3，就可以判断该数能否被3整除．如果这个数足[收稿日期]2009-01—12●[作者简介]王萍(1984一)，女，四川乐山人，硕士研究生，主要从事信息安全中的计算方法研究9万方数据够大使得各位加起来还是位数很大，那么可以继

6、续使用这个方法来判定．同理，我们也可以判定一个大整数是否能被7、11、13等小素数整除．我们先看怎样判定大数能被11整除：因10毫一1(rood11)，故整数(aka‘一l⋯aIao)10=aI·10‘+aI—l·10‘一1+⋯+al·10+ao兰aI(一1)“+aI—l(一1k-,+⋯一aI+ao(mod11)．也就是说，用偶数位数字之和减去奇数位数字之和得到的结果如果能被11整除，则该数能被11整除．再看怎样判定能被7整除：因106兰1(mod7)，故整数可写成：(aka＆一1⋯aIao)lo=aI·10‘+a々一l·10。一1+⋯+al·10+ao兰(ao+lOal+

7、102a2+⋯+105a5)+106(a6+lOa7+102a8+⋯+105a11)+(106)2a12+10口13+102口14+⋯+10％17)+⋯=(a5a4a3a2alao)10+(a11aloa9a8a7a6)lo+(a17a16a15a14a13a12)lo+⋯(mod7)．我们发现，由于106三1(rood7)，就把大整数“分块”，自低位起，6位数为“一块”，然后把分块后的很多个6位数相加再来模7．如果相加后还是大于6位的大整数，可以再用这个方法分块相加算出最后结果，如果能整除7，则这个大整数可以整除