Miller-Rabin素性测试(POJ3641)

一.概念引入         在以往判断一个数n是不是素数时,我们都是采用i从2到sqrt(n)能否整除n.如果能整除,则n是合数;否则是素数.但是该算法的时间复杂度为O(sqrt(n)),当n较大时,时间性能很差,特别是在网络安全和密码学上一般都是需要很大的素数.而从目前来看,确定性算法判断素数的性能都不好,所以可以用MC(蒙特卡洛)概率算法来解决,其中Miller Rabin算法就是其中的很经典的解决方法.下面首先介绍下相关的数学理论。         理论基础：Fermat小定理:若n是素数，则对所有1≤a≤n-1的整数a，有a^(n-1)mod n=1;该定理的逆否命题也成立,即a^(n-1)mod n!=1,则n为合数。但是如果n是素数，就不一定成立了，比如当a=4,n=15时,4^14mod15=1,但是4不是素数而是合数。         不过,从大量数据统计来看,如果满足a^(n-1)mod n=1,则n较大概率为素数。那么,我们把那些使得n原本为合数而被看成素数的a叫做伪证据,n为伪素数。同样从大量数据看出有些伪素数n有很多伪证据a,比如当n=561,a有318个可使得结果判为素数。所以,读者可以去查查强伪素数的概念。 二.POJ3641 　　判断p是否是基于a的伪素数。