素性测试--Miller-Rabin算法

引子

今天（23/8/16），老师问了一个有趣的问题：

出道题给大家, 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 是不是素数？怎么检测？


自己去查了一下相关的一些验证大整数素数的方法，对于其中的Miller-Rabin算法与椭圆曲线确定性算法着手实现了一下，由于这个数字位数还是有点大的，加上这两种算法都是一种概率性测试，两种得出的结果出现了差异（椭圆曲线出了个合数结果）……最后用sagemath验证了一下，给出的结果是素数

这篇就对这两种算法中的Miller-Rabin以初步认识的视角来写一下，当然会很烂啦……

更新(23/8/17)：
老师提醒我CINTA里有……
（刚看到第三章
有点为了解决问题而做事了，对定理没有理解得很好还把费马小定理和拉宾测试混在一起了……
老老实实回归教材。

费马小定理

a^p-1\(\equiv 1 \pmod p\)
p为素数，a不为p的倍数
a 必须满足 gcd(a, n) = 1。

不完善

伪素数：
设 n ∈ Z 为合数，如果存在 a ∈ Z 且 gcd(a, n) = 1，使得下式成立：
a ⁿ⁻¹ ≡ 1 (mod n)
则称 n 是以 a 为基的伪素数（Pseudoprime）。
对一个合数 n，大部分的整数 a < n 都使得等式 aⁿ⁻¹ ≡ 1 (mod n) 成立

Carmichael数：设 n ∈ Z 为合数，对任意 a ∈ Z 且gcd(a, n) = 1，上式成立，则称 n 为 Carmichael 数，或称绝对伪素数。如561。
判定：设 n = q0q1 · · · qk 是一个合数，其中 k > 1，对任意 i，qi 是两两不同的素数且满足(q_i − 1) | (n − 1)。则 n 是 Carmichael 数。

对这种数字进行检测，选中 a 且 gcd(a, n) = 1 的概率就很小，

完善：Miller-Rabin

米勒测试

q 是一个奇数，k 是某个正整数。设 a 是任意选取的整数，且 gcd(a, n) = 1。

如果以下两个条件其中之一得到满足：

1. a^q ≡ 1 (mod n)
2. 存在某个 0 ≤ j ≤ k − 1，使得 a ^2jq ≡ −1 (mod n)

则称 n 通过了以 a 为基的米勒测试。

证明：

费马小定理
有序列：
a^q , a^2q , a<^4q , … a^2k-1q

基本过程：

1. 判断a^q ≡ 1 (mod n) 或 a^q ≡ −1 (mod n) 是否成立，成立则通过米勒测试
2. 不成立则判断a^2q≡-1(mod n)是否成立，成立则通过。
   a ⁿ⁻¹ ≡ 1(mod n) 必然成立，a ⁿ⁻¹=a ^2jq，所以n必然会通过以a为基的米勒测试。

n 不通过米勒测试，则 n 必然是合数，但是如果 n 通过米勒测试，则只说明 n 可能是素数。以下，继续完善。

拉宾的贡献

通过 k 次不同的米勒测试，可以把合数误判为素数的的概率尽可能地降低。
任一次不通过，则 n 是合数，否则 n 就大概率是素数。

伪证据的数量
如果 n 是一个奇合数，则最多有 (n − 1)/4 个整数 a，1 ≤ a ≤ n − 1，使得 n 可以通过以 a 为基的米勒测试。

拉宾测试（估算所需测试次数）
如果 n 是一个奇合数，选取 k 个不同的整数 a，1 ≤ a ≤ n − 1，对 n 进行以 a 为基的米勒测试。则 n 通过所有 k 次米勒测试的概率小于 (1/4)^k