Miller-Rabin 素性检测，是一种概率性的素数测定法，它以费马小定理引出
费马小定理：如果n是一个素数，且a，n的最大公约数等于1，那么a^(n-1) =1 (mod n)。因为费马小定理是一个必要条件，逆命题不成立，但是使逆命题不成立的数非常少，所以可以概率测试；成功率号称在99.99%左右........
二次探测定理：如果n是一个素数，那么对于任意x（0<x<n） ，方程x^2≡1(mod n)的解为x=1,n-1
证明：x^2≡1(mod n)等于x^2-1≡0(mod n)等于(x+1)(x-1)≡0(mod n);由于n是素数，所以x=1,n-1
Miller - Rabin 素性测试: (只考虑正整数)
先假设要测试的数n是素数(若n为1 或 2则要另外判定)
对于测试数n, 将n - 1 分解成 o * 2^k, 其中o表示一个奇数, k为正整数 .(只有k >= 1才能用得上二次探测定理, 下面的说明也假设k >= 1, 其实也就是n >= 3)
于是n能通过以a为底的费马素性测试((a, n) = 1, 可以多选几个a, 提高准确率, 一般选前几个素数, 或其它随机数):
a^(n - 1) ≡1 (mod n)
a^(o * 2^k) ≡1 (mod n)
(a^(o * 2^(k - 1)))^2 ≡1 (mod n)
(a^(o * 2^(k - 1)) mod n)^2 ≡1 (mod n)
由二次探测定理可知 a^(o * 2^(k - 1)) mod n 为 1 或 n - 1
(核心)于是计算: a^(o * 2^(k - 1)) mod n
1.若为n - 1,判定停止(因为无法再用二次探测定理)
2.若为1, 但无法再提取指数中的因子2, 判定也停止(因为无法再用二次探测定理)
3.若为1, 但还可提取指数中的因子2, 则提出此因子, 再次用二次推测定理判定
4.若既不为1, 也不为n - 1, 则表明出现矛盾(与二次控测定理), 推翻n为素数的结论.
最后若不能推翻n为素数, 则n很有可能为素数.那些通过以a为底的Miller - Rabin测试的数,称为以a为底的强伪素数.
优化:
若n为以a为底的强伪素数 <=> 有且只有一个(因为两个或以上同时成立会出现矛盾)
i = 0, 1, 2, ... , k - 1, 使a^(o * 2^i) mod n = n - 1 或 a^o mod n = 1 (n >= 3)
证明:
1.当n为以a为底的强伪素数, 假若右边不成立, 但由判定过程可知n不为以a为底的强伪素数.矛盾.故此时右边必成立.
2.当右边条件成立
1)a^o mod n = 1 => a^(o * 2^i) mod n = 1 , i = 0, 1, 2, 3, ... , k - 1
由判定过程可知n一定通过此判定, 一定为以a为底的强伪素数.
2)有且只有一个(因为两个或以上同时成立会出现矛盾)i = 0, 1, 2, ... , k - 1, 使a^(o * 2^i) mod n = n - 1 => a^(o * 2^j) mod n = 1, j = i + 1, i + 2, ... , k - 1
由判定过程可知n一定通过此判定, 一定为以a为底的强伪素数.
故判定过程可改为:
1.将n - 1分解成 o * 2^k.(若n为1 或 2则要另外判定)
2.计算a^o mod n
若为1 或 n - 1, 则此数通过判定.
3.用公式: a^(o * 2^i) mod n = (a^(o * 2^(i - 1)) mod n)^2 mod n 循环计算, i = 1, 2, ... , k - 1 (正是这里减少了运算量)
若为n - 1, 则此数通过判定.
4.到最后还不能跳出判定的数则显然为合数.