Miller-Rabin
费马小定理: 假如a是一个整数，p是一个质数，且a、p互素(a,p)=1, 则a^p≡1(mod p)
费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael.
前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。
在1~100000000范围内的整数中，只有255个Carmichael数。
为此又有二次探测定理 Miller-Rabin算法的一般步骤: 注意
二次探测定理 如果p是一个素数，0
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
1 计算时会用到a^b mod n,应进行一定优化.
2 Miller-Rabin是随机算法
结果的正确率约为 75%,所以应该多次调用该函数,使正确概率提高为1-(1/4)^p
友情提示: 请注意文章的时效性与准确性, 作者不对文章的有效性负责.
Tags: algorithms
Permalink Bookmark on del.icio.us
Last Modified: July 18, 2007 at 8:07 pm