素性测试

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