费马小定理(Fermat theorem): 设p为一素数,而a与p互素,则 a^p - a 必为p的倍数。
利用费马小定理,对于给定的整数n,可以设计一个素数判定算法。通过计算d=2^(n-1)mod n来判定整数n的素性。当d不等于1时,n肯定不是素数;当d等于1时,n则很可能是素数。但也存在合数n使得2^(n-1)≡1(mod n)。例如,满足此条件的最小合数是n=341。为了提高测试的准确性,我们可以随机地选取整数1Carmichael数,前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中,只有255个Carmichael数。
二次探测定理
二次探测定理 如果p是一个素数,0<x<p,则方程x^2≡1(mod p)的解为x=1,p-1
根据以上两个定理,如到Miller-Rabin算法的一般步骤:
0、先计算出m、j,使得n-1=m*2^j,其中m是正奇数,j是非负整数
1、随机取一个b,2<=b
2、计算v=b^m mod n
3、如果v==1,通过测试,返回
4、令i=1
5、如果v=n-1,通过测试,返回
6、如果i==j,非素数,结束
7、v=v^2 mod n,i=i+1
8、循环到5
说明:
Miller-Rabin是随机算法
得到的结果的正确率为 75%,所以应该多次调用该函数,使正确概率提高为 1-(1/4)^p
posted on 2009-03-13 14:20
古月残辉 阅读(976)
评论(0) 编辑 收藏 引用 所属分类:
Theory