随笔-20  评论-16  文章-36  trackbacks-0

费马小定理(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理