米勒-拉宾法

米勒-拉宾算法是一个判断素性的多项式时间概率算法.

由于米勒-拉宾法的非确定性，当我们对判定素数的要求仅为需要偏“是”的判定法时，用米勒-拉宾法比较容易，但是如果我们需要确定解时仍然要依靠速度较慢的其他确定性素性判定法。

其过程如下：

Miller-Rabin(n)

把n-1写成n-1=2^k *m ，其中m是一个奇数

选取随机整数a，使得 1<=a<=n-1

将a^m(mod n)赋值给b,

if b=1(mod n)

then return(“n is prime”)

for 将0赋值给i to k-1

do { if b=-1(mod n)

then return ("n is prime")

else 将b^2(mod n)赋值给b

}

return(“n is composite”)

若n 通过一次测试，则n 不是素数的概率为 25%.