Click to edit Title Slide,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,素性测试,PRIME TESTING,内容的设置,简单判别法,概率判别法,问题的引入,Prime testing,如何有效地确定一个给定的数是否是素数，即素性测试问题,又叫素性检验、素性检测,通常借助合数测试，即通过判断出是合数而证明不是素数,目的：快速生成大素数,分为确定测试和概率测试,确定测试指能肯定被测试的数是素数或合数。,概率测试指在很小的可能性内使测试将复合数判别为素数(或反之)：如果判断为素数，则是合数的概率小于很小的一个数,概率测试需要满足：比确定测试快得多，出错的概率极小,简单判别法,目前几乎没有实用价值,整除判别法,又叫古典判别法,用已知的素数去寻找下一个素数:用不超过,sqrt(n),的整数试除,爱托拉斯散筛法,Eratosthene,的依据,Wilson,阶乘判别法,根据,wilson,定理:,P,素,素数的概率判别法,拟素数,又叫伪素数，更狭义的指通过了素性测试的合数,伪素数、强伪素数和,Carmichael,数,最简单的概率素性测试算法为,Fermat,素性测试,费马小定理不成立一定为合数,费马小定理成立不一定为素数,几个有效素性测试算法的起点和基石,多次重复，降低是拟素数的概率,基本是排除合数的情况,通常计算机实现的都是概率判别法,素数的概率判别法,费马概率判别法,利用费马小定理(,b,n)=1,b,n-1,1(mod n),同余式成立的合数,n,叫以,b,为基的拟素数，或叫基,b,的拟素数,如果合数,n,是以任意互素正整数为基的拟素数，则叫,Carmichael,数，卡米切尔,561,是第一个,对其无法确定它是一个合数，除非碰到它的一个因子,虽被证明无穷多，但非常稀少,素数的概率判别法,费马概率判别法,方法：,给定奇数,n,5和安全参数,t,(1)随机选取整数,b，2b n-1,(2)计算,g=(b,n)，,若,g=1,则,n,合,(3)计算,r,b,n-1,(mod n),若,r=1,则,n,合,(4)若(2)(3)都不能证明是合,则可能素,(5),上述过程重复,t,次，若每次都得到,n,可能素的结果，则,n,是素的概率为,素数的概率判别法,Lehmann,算法,同样利用费马小定理(,b,n)=1,b,n-1,1(mod n),少算一次幂，只需,b,(n-1)/2,1(mod n),素数的概率判别法,Solovay-strassen,概率判别法,利用欧拉判别条件,成立不一定为素数，,n,为合数时成立叫做基,b,的,euler,拟素数,基,b,的,euler,拟素数一定是基,b,的拟素数，逆不成立,素数的概率判别法,Miller-Rabin,素性检验,利用素数的因子只有1和自身，,p,是素数时，则,x,2,1,(mod p),的解为1或-1(,mod p),或者说若,n-1=2,s,t，2|t,则,b,n-1,1=(+1)(+1),(b,t,+1)(b,t,-1),若,n,是素数时，,n|b,n-1,1,则,n,一定整除其中一个因式,如果合数也满足，则称强拟素数,基,b,的强拟素数一定是基,b,的欧拉拟素数,实际用的最多 的,素数的概率判别法,Miller-Rabin,素性检验,方法：,给定奇素,n,3(,n-1=,2,s,m,s,0,m,奇)和安全参数,t,(1)随机选取整数,b，2bn-1；r=0,(2),z=b,m,(mod n),若,z=1,或,n-1，,则,n,可能素，转(8),(3)若,r=s-1，,则,n,合,(4),r+,(5),z=z,2,(mod n),(6),若,z=n-1,则,n,可能素，转,(8),(7)转（3）,(8)上述过程重复,t,次，若每次,n,都可能素，则,n,是素的概率为,总结,素性判断,目的：判断一个数是否是素数,用途：生成素数,方法：古典、确定性、概率性,实用的：大整数计算机素性判断使用概率方法,总结,概率性素性判断,理论依据：费马小定理,不足：费马小定理成立并不一定是素数,导致：拟(/伪,),素数,即本是合数却被误判为素数,解决：重复,最终结果：通过测试的数是素数的概率非常大,总结,概率性素性判断的三种方法,共同依据：,b,n-1,1(mod n)，(b,n)=1,共同措施：,循环：,b+,t-(b,为底，,t,为循环次数，叫安全参数),(,b,n),互质，否则,n,非素,总结,概率性素性判断的三种方法,共同依据：,b,n-1,1(mod n)，(b,n)=1,考虑：左右同时开方后,不同之处：,幂的值：,n-1,(n-1)/2,(n-1),去除2的幂,拟素数：基,b,的费马拟素数、欧拉拟素数、强拟素数,