引子
今天（23/8/16），老师问了一个有趣的问题：
出道题给大家, 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 是不是素数？怎么检测？
自己去查了一下相关的一些验证大整数素数的方法，对于其中的Miller-Rabin算法与椭圆曲线确定性算法着手实现了一下，由于这个数字位数还是有点大的，加上这两种算法都是一种概率性测试，两种得出的结果出现了差异（椭圆曲线出了个合数结果）……最后用sagemath验证了一下，给出的结果是素数
这篇就对这两种算法中的Miller-Rabin以初步认识的视角来写一下，当然会很烂啦……
更新(23/8/17)：
老师提醒我CINTA里有……
（刚看到第三章
有点为了解决问题而做事了，对定理没有理解得很好还把费马小定理和拉宾测试混在一起了……
老老实实回归教材。
费马小定理
ap-1\(\equiv 1 \pmod p\)
p为素数，a不为p的倍数
a 必须满足 gcd(a, n) = 1。
不完善
伪素数：
设 n ∈ Z 为合数，如果存在 a ∈ Z 且 gcd(a, n) = 1，使得下式成立：
a n−1 ≡ 1 (mod n)
则称 n 是以 a 为基的伪素数（Pseudoprime）。
对一个合数 n，大部分的整数 a < n 都使得等式 an−1 ≡ 1 (mod n) 成立
Carmichael数：设 n ∈ Z 为合数，对任意 a ∈ Z 且gcd(a, n) = 1，上式成立，则称 n 为 Carmichael 数，或称绝对伪素数。如561。
判定：设 n = q0q1 · · · qk 是一个合数，其中 k > 1，对任意 i，qi 是两两不同的素数且满足(qi − 1) | (n − 1)。则 n 是 Carmichael 数。
对这种数字进行检测，选中 a 且 gcd(a, n) = 1 的概率就很小，
完善：Miller-Rabin
米勒测试
q 是一个奇数，k 是某个正整数。设 a 是任意选取的整数，且 gcd(a, n) = 1。
如果以下两个条件其中之一得到满足：
- aq ≡ 1 (mod n)
- 存在某个 0 ≤ j ≤ k − 1，使得 a 2jq ≡ −1 (mod n)
则称 n 通过了以 a 为基的米勒测试。
证明：
费马小定理
有序列：
aq , a2q , a<4q , … a2k-1q
基本过程：
- 判断aq ≡ 1 (mod n) 或 aq ≡ −1 (mod n) 是否成立，成立则通过米勒测试
- 不成立则判断a2q≡-1(mod n)是否成立，成立则通过。
a n−1 ≡ 1(mod n) 必然成立，a n−1=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