|
一款可瞬间判定素数的神奇小软件
本人可以给出计算 a^((p-1)/2)mod p 的简洁算法 ,即费马方法 判断一个数是否为素数的 依据
首先 将(p-1)/2 分解为二进制数 ,其系数 计为 (由高到低) b_n,b_(n-1),b_(n-2),...b2,b1,b0.
然后计算 a^2=a1(mod p) a2^2=a2(mod p) a2^2=a3(mod p)
...a_(n-1)^2=a_n (mod p)
再计算 (b0*a)*(b1*a1)*(b2*a2)*...*(b_n*a_n) =m (mod p).m 即为 所求的值
下面给出例子
计算 2^54(mod 109)
2^2=4^2=16^2=38^2=27^2=75 (mod 109)(这里我连写了 ,,实际等号并不存在 ,实为 2^2=4 ,4^2=16,16^2=38 (mod 109)...)
4*16*27*75=129600=108 (mod 109)
该算法的 最坏时间复杂度为 nlog(2)N ,这里,2为底数
[br][br]-=-=-=-=- 以下内容由 wsc810 在 时添加 -=-=-=-=-
[br][br]-=-=-=-=- 以下内容由 wsc810 在 时添加 -=-=-=-=-
不好意思我写错了 ,最坏时间复杂度为 2*log(2)N |
|