信安数学 第11章 素性测试.pptVIP

巫玲 Wuling751@126.com 第11章 素性测试PRIME TESTING 学习目标 理解简单判别法和确定判别法 掌握三种拟素数 掌握概率判别法 课程内容的设置 简单判别法 确定判别法 概率判别法 6.0 问题的引入 Prime testing 如何有效地确定一个给定的数是否是素数，即素性测试问题 又叫素性检验、素性检测 通常借助合数测试，即通过判断出是合数而证明不是素数 目的：快速生成大素数 分为确定测试和概率测试 确定测试指能肯定被测试的数是素数或合数。 概率测试指在很小的可能性内使测试将复合数判别为素数(或反之)：如果判断为素数，则是合数的概率小于很小的一个数 概率测试需要满足：比确定测试快得多，出错的概率极小 6.1 简单判别法 目前几乎没有实用价值 整除判别法 又叫古典判别法 用已知的素数去寻找下一个素数:用不超过sqrt(n)的整数试除 爱托拉斯散筛法Eratosthene的依据 Wilson阶乘判别法 根据wilson定理:P素 = 6.2 确定判别法 莱梅， D.H.Lehmer 原理：欧拉函数与欧拉定理：只要证明 则p素，用阶搭桥 方法：正奇数p1,p-1= ，pi素，若对每个pi都存在ai 满足 和 i=1,2,…,s 则p素 6.2 确定判别法 使用：例1 证明37是素 证明：p-1=36= 对于p1=2 218≡(-5)3.23≡25.(-40)≡-1(mod37) 236≡1(mod37)， 对于p2=3 212≡(-5)2.22≡-48≡-11(mod37) 236≡1(mod37)， 所以37是素 6.2 确定判别法 莱梅， D.H.Lehmer 定理证明的思路： 只要证明此时 ，也就是 |p-1,p-1| ,先证p-1| ， 反证：设 |p-1,且 | ，设ordp(ai)=ki则ki|p-1, ki|(p-1/pi) 所以 pi|ki,否则ki|(p-1/pi) 所以 |ki,否则设 |ki(0jr), (p-1/pi)= 所以r-jr-1,所以j1,所以j=0 因为ki| ,所以 | 矛盾，所以p-1| 再因为 =p-1 所以 6.2 确定判别法 普罗兹，proth Lehmer中不再全部分解p-1，部分分解，更容易实现 方法：正奇数p1,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 确定判别法 普罗兹，proth 定理证明的思路：证明条件满足时p的因子只有1和自身 证明：记?p(ai)=s,所以s|p-1,s|m 所以q|s(由上一个定理的证明过程来) 又s|?(p) ,故q|?(p) 设p= 则q|(qm+1)∏(pi-1) 所以q|∏(pi-1) 所以至少存在一个pi使q|pi-1 因为q奇，所以2q|pi-1，所以pi? 1+2q 又p-1≡0(mod 2q) 则 p/pi≡1(mod 2q) 若p = pi,则p/pi = 1 所以 p/pi = 1+2qt ? 1+2q 所以p=pi.p/pi ?(1+2q)2 p，矛盾 所以p = pi所以p素 6.2 确定判别法 波克林顿（pocklington） 将proth中对m,q的限制取消，转换另外的条件 分圆域素性测试 目前最强有力的实用算法之一 AKS算法 2002年8月，印度Manindra Agrawal和他的两个学生Neeraj Kayal和Nitin Sanexa设计了一个被称为AKS的算法，是这一领域的一个重要突破 该算法是一个用于素性测试的多项式时间的确定算法。 6.3 素数的概率判别法 拟素数 又叫伪素数，更狭义的指通过了素性测试的合数 伪素数、强伪素数和Carmichael数 最简单的概率素性测试算法为Fermat素性测试 费马小定理不成立一定为合数 费马小定理成立不一定为素数 几个有效素性测试算法的起点和基石 多次重复，降低是拟素数的概率 基本是排除合数的情况 通常计算机实现的都是概率判