信安数学 第11章 素性测试

《信安数学 第11章 素性测试》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、巫玲Wuling751@126.com第11章素性测试PRIMETESTING学习目标理解简单判别法和确定判别法掌握三种拟素数掌握概率判别法课程内容的设置简单判别法确定判别法概率判别法6.0问题的引入Primetesting如何有效地确定一个给定的数是否是素数，即素性测试问题又叫素性检验、素性检测通常借助合数测试，即通过判断出是合数而证明不是素数目的：快速生成大素数分为确定测试和概率测试确定测试指能肯定被测试的数是素数或合数。概率测试指在很小的可能性内使测试将复合数判别为素数(或反之)：如果判断

2、为素数，则是合数的概率小于很小的一个数概率测试需要满足：比确定测试快得多，出错的概率极小6.1简单判别法目前几乎没有实用价值整除判别法又叫古典判别法用已知的素数去寻找下一个素数:用不超过sqrt(n)的整数试除爱托拉斯散筛法Eratosthene的依据Wilson阶乘判别法根据wilson定理:P素<=>6.2确定判别法莱梅，D.H.Lehmer原理：欧拉函数与欧拉定理：只要证明则p素，用阶搭桥方法：正奇数p>1,p-1=，pi素，若对每个pi都存在ai满足和i=1,2,…,s则p素6.2确定判

3、别法使用：例1证明37是素证明：p-1=36=2.2.3.3对于p1=2218≡(-5)3.23≡25.(-40)≡-1(mod37)236≡1(mod37)，对于p2=3212≡(-5)2.22≡-48≡-11(mod37)236≡1(mod37)，所以37是素6.2确定判别法莱梅，D.H.Lehmer定理证明的思路：只要证明此时，也就是

4、p-1,p-1

5、,先证p-1

6、，反证：设

7、p-1,且

8、，设ordp(ai)=ki则ki

9、p-1,ki

10、(p-1/pi)所以pi

11、ki,否则ki

12、(p-1/p

13、i)所以

14、ki,否则设

15、ki(0r-1,所以j<1,所以j=0因为ki

16、,所以

17、矛盾，所以p-1

18、再因为<=p-1所以6.2确定判别法普罗兹，prothLehmer中不再全部分解p-1，部分分解，更容易实现方法：正奇数p>1,p-1=mq，q奇素且，若存在a使和则p素6.2确定判别法使用：例1证明37是素证明：36=12.3,m=12,q=3,212≡(-5)2.22≡-48≡-11(mod37)236≡1(mod37)所以37是素6.2确定判别法普罗兹

19、，proth定理证明的思路：证明条件满足时p的因子只有1和自身证明：记p(ai)=s,所以s

20、p-1,s

21、m所以q

22、s(由上一个定理的证明过程来)又s

23、(p),故q

24、(p)设p=则q

25、(qm+1)∏(pi-1)所以q

26、∏(pi-1)所以至少存在一个pi使q

27、pi-1因为q奇，所以2q

28、pi-1，所以pi1+2q又p-1≡0(mod2q)则p/pi≡1(mod2q)若p=pi,则p/pi=1所以p/pi=1+2qt1+2q所以p=pi.p/pi(1+2q)2>p，矛盾所以p=pi所以p

29、素6.2确定判别法波克林顿（pocklington）将proth中对m,q的限制取消，转换另外的条件分圆域素性测试目前最强有力的实用算法之一AKS算法2002年8月，印度ManindraAgrawal和他的两个学生NeerajKayal和NitinSanexa设计了一个被称为AKS的算法，是这一领域的一个重要突破该算法是一个用于素性测试的多项式时间的确定算法。6.3素数的概率判别法拟素数又叫伪素数，更狭义的指通过了素性测试的合数伪素数、强伪素数和Carmichael数最简单的概率素性测试算法为F

30、ermat素性测试费马小定理不成立一定为合数费马小定理成立不一定为素数几个有效素性测试算法的起点和基石多次重复，降低是拟素数的概率基本是排除合数的情况通常计算机实现的都是概率判别法6.3素数的概率判别法费马概率判别法利用费马小定理(b,n)=1,bn-1≡1(modn)同余式成立的合数n叫以b为基的拟素数，或叫基b的拟素数如果合数n是以任意互素正整数为基的拟素数，则叫Carmichael数，卡米切尔561是第一个对其无法确定它是一个合数，除非碰到它的一个因子虽被证明无穷多，但非常稀少6.3素数的

31、概率判别法费马概率判别法方法：给定奇数n5和安全参数t(1)随机选取整数b，2≤b≤n-1(2)计算g=(b,n)，若g=1,则n合(3)计算r≡bn-1(modn),若r=1,则n合(4)若(2)(3)都不能证明是合,则可能素(5)上述过程重复t次，若每次都得到n可能素的结果，则n是素的概率为6.3素数的概率判别法Lehmann算法同样利用费马小定理(b,n)=1,bn-1≡1(modn)少算一次幂，只需b(n-1)/2≡±1(modn)6.3素数的概率判别法Solovay-strassen