素性测试.pptx

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