(实际上是摘抄wiki)
突然想起来还没写过MR，于是来写一篇，同时写一些别的东西。
众所周知，有个东西叫费马小定理。人们发现费马小定理在膜数不是素数的时候有不小的可能性是不成立的，所以就考虑用这个来判定一个数是不是素数，也就是找一些$a$，如果$a^{n-1}\neq 1\pmod{n}$，那么就说明$n$不是素数。
固定一个$a$很容易就没了。让一个$a$没了的数$n$被称为关于$a$的费马伪素数。
要枚举所有的$a$的话，还不如直接枚举$n$的因数，所以我们可以随几个$a$，越随越牛逼。这个算法称为 费马素性测试。
然而这个东西飞了，因为它会被一类称为 卡迈克尔数 的数给干翻。这一类数就是对于所有的$a\perp n$，都有$a^{n-1}\equiv 1\pmod{n}$的数$n$。
尽管可以证明不存在对于所有$a$都有$a^{n-1}\equiv 1\pmod{n}$的合数，卡迈克尔数还是很要命，因为面对卡迈克尔数，费马素性测试相当于在随机找这个数的因子。
卡迈克尔数有无限个，并且可以证明$n$以内的卡迈克尔数个数是$\Omega(n^{\frac{2}{7}})$。判定一个数$n$是不是卡迈克尔数，它首先不能有平方因子，然后对于它的所有素因子$p$，都有$p-1\mid n-1$，所以它可以使用Pollard-rho在期望$O(n^{\frac{1}{4}})$时间内计算，或者埃筛做到$O(n\log\log n)$处理前$n$个，我不理解是否有线筛做法。
那么如何才能把费马素性测试变得更好呢?显然的想法是换一个结论或者加上更多的结论，这导出了很多不同的素性测试，我们来扯一下MR和AKS。
Miller-Rabin
MR基于一个费马小定理的加强版，称为 二次探测定理。草我怎么记得hash table里面有个二次探查（
费马小定理说明$a^{n-1}\equiv 1\pmod{n}$，也就是$a^{n-1}-1\equiv 0\pmod{n}$。要做素性测试，$n$首先得是奇数，于是$n-1$就是偶数，我们假设它是$2^km$。于是用平方差拆开，我们得到一个看起来像这样的东西
\[(a^m-1)\prod_{i=0}^{k-1}(a^{2^im}+1)\equiv 0\pmod{n}\]如果$n$是素数，那么其中必须有一项是$0$，否则有可能它们都不是$0$。我们求出$a^m$，然后反复平方即可。所以这是单次一个$\log$的，这里认为加减乘除是$O(1)$的。
可以证明对于每个合数，在所有与它互素的基数$a$中(不互素的情况可以求一个$\gcd$来判掉)，都有至少$3/4$的$a$可以证明它是合数，并且在大部分数上这个比例要更高，大概是$7/8$。怎么证?一会再说。
有些时候我们会想要确定性的MR，因为随机的正确性实在是不能保证。选取七个数$2,325,9375,28178,450775,9780504,1795265022$就可以覆盖$2^{64}$，但是这七个数不太好记，场上可以选取前十二个素数。注意在实现的时候，比如要测试$114514$的素性，我们不能跳过比它大的基数比如$1795265022$，而是应该先把这个数对$114514$取膜，如果得到结果是$0$则跳过，否则正常进行。
实际上MR有一个任意值域的确定性版本，如果广义黎曼猜想是正确的，测试前$O(\log^2 n)$个数就足够了，所以……如果你选择使用它，然后它锅了，那么你就可以拿到诺贝尔数学奖。
这一部分是MR正确率的证明。算导上有一个简单的$\frac{1}{2}$的证明，不过那个没啥意思（
证明的构造上来看会比较奇怪，不过看到后面你会全明白了。思路也很粗暴，就是先放缩成能算的东西，然后硬算。
二次探测定理 对于一个$>9$的奇合数$n=2^km+1$($m$是奇数)，有不超过$\frac{\varphi(n)}{4}$个和$n$互素的数$x$，满足$x^m=1$或者某个$x^{2^im}=-1$，其中$0\leq i<k$。
证明 放缩一下。考虑$n$的分解，对于它的每个素因数$p$，我们从$p-1$中尽可能提取$2$，设提取了$l_p$个，取最小的$l_p$设为$l$。
考虑方程$x^{2^{l-1}m}\equiv\pm 1\pmod{n}$，容易发现满足$x^m=1$的$x$必然满足这个方程。
而对于满足某个$x^{2^im}\equiv -1$的$x$，为了证明它也满足这个方程，我们显然是希望证明$i\leq l-1$，这样就有$x^{2^{l-1}m}\equiv (-1)^{2^{l-i-1}}\equiv\pm 1$。
考虑$x^{2^{i+1}m}$膜$n$的任意一个素因子$p$得到$1$，$x^{2^im}$膜$n$的任意一个素因子$p$也得到$-1$，这说明$x$膜$p$的阶是$2^{i+1}$的因数而又不是$2^i$的因数，所以这个阶必然就是$2^{i+1}$。同时$x$膜$p$的阶应该是$p-1$的因数，所以$2^{i+1}\mid p-1$，这就很好!
所以问题变为证明$x^{2^{l-1}m}\equiv\pm 1\pmod{n}(x<n,x\perp n)$的解数不超过$\frac{\varphi(n)}{4}$。
注意到$x^{2^{l-1}m}\equiv 1\pmod{n}(x<n,x\perp n)$的数，必然膜每个$n$中的$p^k$还是$1$，根据CRT我们知道这个反过来也成立，于是$x^{2^{l-1}m}\equiv 1\pmod{n}(x<n,x\perp n)$的解数等于各$x^{2^{l-1}m}\equiv 1\pmod{p^k}(x<p^k,x\perp n)$的解数之积。$x^{2^{l-1}m}\equiv -1\pmod{n}(x<n,x\perp n)$是一样的。
考虑怎么算$x^{2^{l-1}m}\equiv 1\pmod{p^k}(x<p^k,x\perp n)$的解数。你发现$p^k$存在原根，所以可以取离散对数，于是这相当于让$\varphi(p^k)$个$x$都在一个环上前进了$m2^{l-1}$步。
根据经典结论，从每个和$p^k$互素的数的起点向终点连边，会形成$\gcd(\varphi(p^k),m2^{l-1})$个环，而不互素的数不会掺和进来，因为取幂之后它们必然还包含$p$作为因子或者变成了$0$。每个环上会有一个数转到$1$，所以一共有$\gcd(\varphi(p^k),m2^{l-1})=\gcd((p-1)p^{k-1},m2^{l-1})=\gcd(p-1,m)2^{l-1}$个解。
所以，$x^{2^{l-1}m}\equiv\pm 1\pmod{n}(x<n,x\perp n)$的解数就是
\[2\prod_{p\mid n}\gcd(p-1,m)2^{l-1}\]我们就要证明这个式子
\[2\frac{\prod_{p\mid n}\gcd(p-1,m)2^{l-1}}{\varphi(n)}\leq\frac{1}{4}\]根据积性拆开$\varphi$
\[2\prod_{p^k\parallel n}\frac{\gcd(p-1,m)2^{l-1}}{(p-1)p^{k-1}}\leq\frac{1}{4}\]注意到左边的每个分数，都有上面是下面的真因子，因为$p-1$是偶数而$m$是奇数，那么$\gcd(p-1,m)$必然是$p-1$的真因子，而$2^{l-1}$必然是$p^{k-1}$的因子($l-1$就是为了凑这个)，所以我们知道，如果$n$有$c$个素因子，那么这个式子的值必然不超过$2^{1-c}$，当$c\geq 3$的时候这个式子就必然成立了。
当$c=2$的时候，继续考虑两个素因子的次数，你发现它们都不能超过$1$，因为$2^{1-c}$已经是$\frac{1}{2}$了，如果存在一个二次因子，那么左边至多是$\frac{1}{2}\cdot\frac{1}{3}=\frac{1}{6}$。
现在只剩下$n=pq$和$n=p^k$的情况了。先考虑前者，化一下式子，我们要证明
\[\frac{\gcd(p-1,m)2^l}{p-1}\cdot\frac{\gcd(q-1,m)2^l}{q-1}\leq\frac{1}{2}\]刚才我们说明了两个分数都是$\frac{1}{k}$的形式，所以如果这个式子要不成立，那么两个分数必然都是$1$，从而$p-1=\gcd(p-1,m)2^l,q-1=\gcd(q-1,m)2^l$。
一个自然的想法是从这个推出$p,q$相等。首先我们知道$p-1,q-1$中$2$的次数必然都是$l$，因为$m$是奇数。所以我们也知道$p-1,q-1$的奇数部分(除掉所有$2$之后剩下的部分)都是$m$的因子。
考虑$pq=m2^k+1$，我们把它对$p-1$的奇数部分取膜，会得到$q\equiv 1\pmod{p-1}$，也就是$q-1\bmod{p-1}=0$，反过来也是一样的。从而我们知道$p-1,q-1$的奇数部分互为倍数，于是它们相等。刚才已经论证了它们的$2$的幂次相等，于是必然有$p=q$。
最后是$n=p^k$，你发现要想让上面那个式子不成立，必然有$p^{k-1}<4$，所以唯一的方案是$n=3^2=9$，这就是为什么一开始限制$n>9$。
AKS
抽代要光看网上的资料，学起来好像不容易（
AKS也基于一个费马小定理的加强版，但是这个足够强以至于他们导出了一个确定性并且不依赖任何未证明结论的算法。AKS的论文题目是 Primes is in P，意思是他们在多项式时间内解决了素数判定的问题。
作为一个牛逼算法，AKS不需要任何数学分析的内容，它所有的内容都是初等的，然而还是很困难（所以我只翻译最简单的版本了
考虑在膜素数$n$下，必然有$(x+a)^n\equiv x^n+a\pmod{n}$，这个可以用二项式定理和费马小定理得到。同时，我们发现如果$n$不是素数且$a\perp n$，这个式子必然不成立，因为考虑$n$的素因子$p^k$，这个式子的$n-p$次项是$\binom{n}{p}a^{n-p}x^p$，注意到$a^{n-p}$和$p$互素，$\binom{n}{p}=\frac{n^\underline{p}}{p!}$中$p$的幂次是$p^{k-1}$，所以这个系数不可能被$p^k$整除，于是这个式子膜$p^k$不成立，那么膜$n$也不成立。
现在问题是这个多项式长度是$n$，无法快速计算。于是我们就需要一个强有力的结论，可以极大缩减这个东西的长度。
分圆多项式
$n$次分圆多项式$\Phi_n$指的是一个次数最小的整系数不可约多项式，使得它整除$x^n-1$而不整除任意$k<n$的$x^k-1$。$n$次分圆多项式是唯一的。呃当然它有很多等价定义，原始的定义是以所有$n$次本原单位根为根的多项式。
极小多项式
一个元素在它所属某个域上的 极小多项式，指的是以它为根的最低次首一多项式。这个多项式必然是唯一的。
结论是如果某个元素$a$，$1,a,a^2,a^3,…$张成有限维的空间，那么$a$的极小多项式度数就是它张成空间的维度。
经典结论1 在$\mathbf{F}_p[x]$中，$n$次分圆多项式$\Phi_n$会被分解成$\frac{p-1}{\mathrm{ord}_n(p)}$个$\mathrm{ord}_n(p)$次不可约多项式。
证明 考虑设随便一个$n$次本原单位根是$\omega$，那么根据原根的知识我们知道$\omega\in\mathbf{F}_{p^k}$当且仅当$n\mid p^k-1$，这个又等价于$p^k\equiv 1\bmod{n}$。
考虑取$k=\mathrm{ord}n(p)$，那么必有$\omega\in\mathbf{F}{p^k}$。因为是阶，所以$\omega$不能存在于$\mathbf{F}{p^k}$的任何真子域中，否则阶就不最小了。所以我们知道$\omega$在$F{p^k}$上的极小多项式恰好是$k$次的。
因为$\omega$是$\Phi_n$的根，那么$\Phi_n$必然包含$\omega$的极小多项式作为因子，于是$\Phi_n$必然可以分解成若干个$\mathrm{ord}_n(p)$次不可约多项式的积。
理想和商环
一个环的一个理想是它的一个子集，这个子集和加法构成交换群，而它的乘法具有吸收性，也就是说对于原环中的任意一个元素，它乘上理想中的一个元素，结果必然在这个理想中。比如在整数环$\mathbf{Z}$上，对于任意$n$，$n\mathbf{Z}$是一个理想，因为一个数乘上$n$的倍数还是$n$的倍数。
一个环对它的一个理想的商还是一个环，如果环中两个元素的差存在于理想中，那么商环中这两个元素将被合并入一个等价类。
定义对$a,b$取膜，其中$a$是多项式而$b$是数，表示对$a$取膜，系数对$b$取模。
一个环除以其中一个元素，说的是环中所有元素对这个元素取膜。
AKS定理(一) 现在有$n$，素数$q,r$，一个有限集$S$。如果满足下面这些条件，那么$n$必然是素数幂 :
-
$q\mid r-1$，且$n^{\frac{r-1}{q}}\bmod{r}\neq 0,1$
-
$S$足够大以至于$\binom{\vert S\vert+q-1}{\vert S\vert}\geq n^{2\lfloor\sqrt{r}\rfloor}$
-
对于$S$中每一对不同的$b,b^\prime$，有$n\perp b-b^\prime$
-
对于$S$中每一个$b$，有$(x+b)^n\equiv x^n+b\pmod{x^r-1,n}$
。
证明 这个结论看起来太牛逼了。
先找一个$n$的素因子$p$，使得$p^{\frac{r-1}{q}}\bmod{r}\neq 0,1$。如果没有这样的素因子，那么第一个条件必不可能成立。下面我们默认所有的多项式运算都是在$F_p[x]$上，也就是系数膜$p$的多项式域。
把$(x+b)^n\equiv x^n+b\pmod{x^r-1}$中的$x$换元为$x^{n^i}$，我们得到$(x^{n^i}+b)^n\equiv x^{n^{i+1}}+b\pmod{x^r-1}$。
注意到$(x^{n^{i+1}}+b)^n\equiv x^{n^{i+1}}+b\pmod{x^r-1}$，我们发现它好像自己套自己了，于是可以知道$(x+b)^{n^i}\equiv x^{n^i}+b\pmod{x^r-1}$。根据费马小定理，我们知道$(x+b)^{n^ip^j}\equiv(x^{n^i}+b)^{p^j}\equiv x^{n^ip^j}+b\pmod{x^r-1}$，这个式子对于任意$i,j\geq 0$都成立。
考虑所有$0\leq i,j\leq\sqrt{r}$的$n^ip^j$。它们膜$r$只有$r$种取值，而一共有$(\lfloor\sqrt{r}\rfloor+1)^2$对$i,j$，于是必然存在不同的两对$(i,j),(k,l)$使得$n^ip^j,n^kp^l$膜$r$的值相同，设$t=n^ip^j,u=n^kp^l$，于是我们知道$x^t\equiv x^u\pmod{x^r-1}$，于是根据上面的结论我们知道$(x+b)^t\equiv (x+b)^u\pmod{x^r-1}$。注意到这些数都在$n^{2\lfloor\sqrt{r}\rfloor}$以内，所以$\vert t-u\vert<n^{2\lfloor\sqrt{r}\rfloor}$。
然后根据前面分圆多项式的结论，我们找到一个$r$次分圆多项式的因子$h$，它的次数必然是$\mathrm{ord}_r(p)$。根据条件可以知道$\mathrm{ord}_r(p)$是$q$的一个倍数，于是$h$的次数至少是$q$。
现在我们知道$(x+b)^t\equiv (x+b)^u\pmod{h}$。注意到由于$h$至少是$2$次的，$x+b$必然存在于$(F_p[x]/h)^\ast$中。设$G$是$x+b$们生成的，$(F_p[x]/h)^\ast$的子群，那么$G$中每个元素$g$都满足$g^t=g^u$，也即$g^{\vert t-u\vert}=1$。
注意到$G$至少有$\binom{\vert S\vert+q-1}{\vert S\vert}\geq n^{2\lfloor\sqrt{r}\rfloor}>\vert t-u\vert$个元素，这是因为我们可以选若干个$(x+b)^e$这样的东西，只要各$e$之和不超过$h$的次数就不会发生取膜，而$h$的次数至少是$q$，于是用隔板法可以算出这样的元素至少有$\binom{\vert S\vert+q-1}{\vert S\vert}$ 个。条件限制了对于$S$中每一对不同的$b,b^\prime$，有$n\perp b-b^\prime$，所以显然$p\perp b-b^\prime$，所以只要不发生取膜，就不会出现重复。
你发现$g^{\vert t-u\vert}=1$这个方程，在膜不可约多项式$h$的多项式域上不可能有超过$\vert t-u\vert$个非零解，除非$t=u$。于是$n^ip^j\equiv n^kp^l\pmod{r}$。如果$n$不是$p$的幂，那么必然有$i=k$，于是$p^j\equiv p^l\pmod{r}$，这说明$j=l$，不符合之前的假设。于是$n$必然是$p$的幂。
AKS定理(三) 现在有互素的正整数$n>1,r$，令$v=\mathrm{ord}_r(n)$，还有一个有限集$S$。如果满足下面这些条件，那么$n$必然是素数幂 :
-
$S$足够大以至于$\binom{\vert S\vert+\varphi(r)-1}{\vert S\vert}\geq n^{2d\lfloor\sqrt{\varphi(r)/d}\rfloor}$，其中$d$是任意$\frac{\varphi(r)}{v}$的因数
-
对于$S$中每一对不同的$b,b^\prime$，有$n\perp b-b^\prime$
-
对于$S$中每一个$b$，有$(x+b)^n\equiv x^n+b\pmod{x^r-1,n}$
。
这个比起 AKS定理(一) 看起来要更困难(因为里面有很多的$\varphi$?可能只是我觉得吧)，然而它导出了更简单的AKS算法，所以我们还是抄一下吧。证明思路是类似的?
证明 设$p$是$n$的随便一个素因子。考虑膜$r$的正整数乘法群，它有$\varphi(r)$个元素。它膜掉$n,p$的生成子群之后(也就是把所有$\frac{x}{y}$为某个$n^ap^b$的元素$x,y$合并，留下最小的作为等价类代表元)，设它还剩下$d$个数，把这些数分别设为$m_1,…,m_d$。$n$在$\mathbf{Z}/n$中的生成子群大小是$v$，而$n,p$的生成子群大小是$\frac{\varphi(r)}{d}$，所以必然有$v\mid\frac{\varphi(r)}{d}$，于是$d\mid\frac{\varphi(r)}{v}$。
以下所有多项式操作系数膜$p$。与刚才同理，我们可以证明对于$b\in S$，有$(x^{m_w}+b)^{n^ip^j}\equiv x^{n^ip^jm_w}+b\pmod{x^r-1}$。
考虑所有$0\leq i,j\leq\sqrt{\varphi(r)/d}$的$n^ip^j$。刚才我们说明了它们膜$r$只有$\varphi(r)/d$种取值，而一共有$(\lfloor\sqrt{\varphi(r)/d}\rfloor+1)^2$对$i,j$，于是必然存在不同的两对$(i,j),(k,l)$使得$n^ip^j,n^kp^l$膜$r$的值相同，设$t=n^ip^j,u=n^kp^l$，于是我们知道$x^t\equiv x^u\pmod{x^r-1}$，于是根据上面的结论我们知道对于$m_w$有$(x^{m_w}+b)^t\equiv (x^{m_w}+b)^u\pmod{x^r-1}$。注意到这些数都在$n^{2\lfloor\sqrt{\varphi(r)/d}\rfloor}$以内，所以$\vert t-u\vert<n^{2\lfloor\sqrt{\varphi(r)/d}\rfloor}$。
还是找一个$r$次分圆多项式的不可约因子$h$，它的次数应该是$\mathrm{ord}_p(r)$。设群$G$是$x^{m_w}+b$们生成的膜$h$乘法群，那么对于群中任意元素$g$，根据刚才的结论我们知道$g^t=g^u$。
然后我们还是证明$G$中有至少$\vert t-u\vert+1$个元素以此证明$t=u$，但是这里的过程比较奇怪。考虑$G^d$，这里的乘法是笛卡尔积，它至少有$\binom{\vert S\vert+\varphi(r)-1}{\vert S\vert}>n^{2d\lfloor\sqrt{\varphi(r)/d}\rfloor}\geq (\vert t-u\vert+1)^d$个元素，它们是由若干个
\[\prod_{b\in S}(x^{m_1}+b)^{e_b},\prod_{b\in S}(x^{m_2}+b)^{e_b},...,\prod_{b\in S}(x^{m_d}+b)^{e_b}\]乘起来得到的东西，只要$\sum\limits_{b}e_b\leq\varphi(r)-1$就不会发生取膜。剩下的部分就跟前面一样了，但是如何证明它们互不相同?这好像不简单了。
跟前面一样我们知道，因为对于$b,b^\prime\in S$，有$n\perp b-b^\prime$，所以$\prod_{b}(x+b)^{e_b}$们是互不相同的。我们将这个多项式称为$e$，下面我们证明对于另一个类似定义的多项式$f$，$e(x^{m_1}),…,e(x^{m_d})$和$f(x^{m_1}),…,f(x^{m_d})$不全相同。假设它们全相同，根据前面的结论我们知道$e(x^{m_w})^{n^ap^v}\equiv e(x^{n^ap^vm_w})\pmod{h}$，所以$e(x^{n^ap^vm_w})\equiv f(x^{n^ap^vm_w})\pmod{h}$。考虑$g=e-f$，对于$c<r,c\perp r$的$c$，根据序列$m$的定义，$c$在膜$r$下必然可以表示为某个$n^ap^vm_w$，于是$g(x^c)\equiv g(x^{n^ap^vm_w})\pmod{x^r-1}$，于是根据$g$的定义有$g(x^c)\equiv 0\pmod{x^r-1}$，而根据$h$的定义有$g(x^c)\equiv 0\pmod{h}$，这等于是说$y^c$是$g(y)$在$\mathbf{F}_p[y]/h(y)$上的一个根。注意到$y^c$们在膜$h$下是不同的，于是根据原根的相关知识，我们知道$\prod\limits_c(x-y^c)$就是分圆多项式$\Phi_r$。既然它的所有根都是$g$的根，它必然是$g$的一个因子，于是$e\equiv f\pmod{\Phi_r}$。$e,f$的次数都不超过$\varphi(r)-1$，于是必然有$e=f$。
好了这就证完了。
为什么没有第二形式?因为论文里好像没怎么用到它（
下面请 全 体 起 立，我们要证明 Primes is in P。
有了AKS定理，AKS算法就很简单了。
首先判掉$n$是完全$k$次方的情况，这个显然可以很快的搞定。
计算$N=2n(n-1)(n^2-1)(n^3-1)\cdots(n^{4\lceil\lg n\rceil^2}-1)$，找到最小的不整除$N$的数$r$。这一步的复杂度，考虑$N$以上第一个$2^k$，这个$k$据说不超过$(8+(1))\lg^5 n$。注意到$2k$以内的素数乘积$>2^k$，它们不可能全都整除$N$，于是$r\leq 2k=O(\log^5 n)$。这一步是为了保证$v=\mathrm{ord}_r(n)$足够大。
判断$n$是不是$r$以内的素数，或者它存在$r$以内的因子。
取$S={1,2,…,r}$，使用AKS定理，检查是否对于任意$b\in S$，有$(x+b)^n\equiv x^n+b\pmod{x^r-1}$。如果成立那么$n$是素数，否则$n$不是。
这个的正确性是显然的，因为$1,…,r$任意两个的差都和$n$互素(不然直接输出合数了)；$v=\mathrm{ord}_r(n)>4\lceil\lg n\rceil^2$，因此如果$d\mid\frac{\varphi(r)}{v}$，那么$d\leq\frac{\varphi(r)}{4\lg^2 n}$，于是$2d\sqrt{\varphi(r)/d}=\sqrt{4d\varphi(r)}\leq\varphi(r)/\lg n$，于是$n^{2d\lfloor\sqrt{\varphi(r)/d}\rfloor}\leq 2^\varphi(r)$。同时$S$的大小是$r$，而$\binom{\vert S\vert+\varphi(r)-1}{\vert S\vert}\geq\binom{2\varphi(r)}{\varphi(r)+1}\geq 2^{\varphi(r)}$，所以就结束了。
如果爆力实现，主要问题在于怎么膜$O(\log^5 n)$级别的$r$下计算那些$(x+b)^n$。我们需要计算$O(\log^5 n)$次长度为$O(\log^5 n)$的带多项式取模的快速幂，并且如果使用法法塔，整数运算需要$\tilde{O}(\log n)$，那么总共就需要$\tilde{O}(\log^{12} n)$。离谱。
关于AKS的优化?可能以后会写吧。