多项式复杂度内的素性检测算法
PRIMES is in P

引理 1.1 $\forall a,b,c\in\mathbb Z$，$m\in\mathbb N^+$，且 $(m,c)\xlongequal{\text{def}}\operatorname{GCD}(m,c)=1$，则当 $ac\equiv bc\pmod m$ 时，$a\equiv b\pmod m$。

证明：条件$\rArr ac-bc\equiv0\pmod m\rArr (a-b)c\equiv 0\pmod m$。因 $m,c$ 互素，故可约去 $c$，得 $a-b\equiv0\pmod m$。即得。

引理 1.2 $\mathbb Z\ni m>1$，$b\in\mathbb Z$，$(m,b)=1$。若 $a_1,a_2,\cdots,a_m$ 是模 $m$ 的一个完全剩余系，则 $ba_1,ba_2,\cdots,ba_m$ 也是模 $m$ 的一个完全剩余系。

完全剩余系：在模 $m$ 的剩余类中各取一个元素，这 $m$ 个数构成了模 $m$ 的完全剩余系。

剩余类：根据整数 $a\in\mathbb Z$ 除以 $n$ 得到的余数将 $\mathbb Z$ 划分为 $n$ 个等价类，$a$ 所在的等价类记作 $[a]$。又称同余类。

证明：反设存在 $1\leqslant i<j\leqslant m$ 满足 $ba_i\equiv ba_j\pmod m$，则根据引理 1.1 得 $a_i\equiv a_j\pmod m$。这不满足 $a[i],a[j]$ 构成模 $m$ 的完全剩余系，矛盾。故对于 $\forall 1\leqslant i<j\leqslant m$，$ba_i\not\equiv ba_j\pmod m$，即它们构成完全剩余系。

证明：对于素数 $p$，构造模 $p$ 的完全剩余系

$$P=\{1,2,\cdots,p-1\}$$

因为 $(a,p)=1$ （$p$ 是素数，$a$ 不是 $p$ 的倍数，故两者互素），由引理 1.2 得

$$A=\{a,2a,\cdots,(p-1)a\}$$

也是模 $p$ 的完全剩余系。由完全剩余系的性质：

$$1\cdot2\cdots(p-1)\equiv a\cdot2a\cdots(p-1)a\pmod p$$

即 $(p-1)!\equiv(p-1)!\cdot a^{p-1}\pmod p$。 显然 $((p-1)!,p)=1$。两侧约去 $(p-1)!$，即得

$$a^{p-1}\equiv1\pmod p$$

设 $K$ 为数域，$\mathcal O_k$ 为 $K$ 的整数环，$a$ 为 $\mathcal O_k$ 的一个理想，$N_a$ 为非零理想的绝对范数，$K$ 上的戴德金 $\zeta$ 函数

$$\zeta_K(s)=\sum_a\frac1{(N_a)^s}$$

其中 $s$ 为实部大于 $1$ 的所有复数，求和运算对所有非零理想 $a$ 进行，猜想 $\zeta_K(s)$ 的所有非平凡零点的实部都为 $\dfrac12$。
当数域 $K$ 取 $\mathbb Q$，$\mathcal O_k$ 取 $\mathbb Z$ 时记为黎曼猜想。

整数 $a,m$ 互素，$m$ 的因式分解式为 $m=p_1p_2\cdots p_r$，则定义

$$\left(\frac am\right)=\left(\frac a{p_1}\right)\left(\frac a{p_2}\right)\cdots\left(\frac a{p_r}\right)$$

其中 $\left(\dfrac a{p_i}\right)$ 是勒让德符号：

$$\left(\frac ap\right)=\begin{cases} 0,&a\equiv0\pmod p\\ 1,&a\not\equiv0\pmod p\wedge \exists x\in\mathbb Z, x^2\equiv a\pmod p\\ -1,&\neg(\exists x\in\mathbb Z,x^2\equiv a\pmod p)\\ \end{cases}$$

$\tilde O(g(n))$ 指 $O(g(n)\log^k(n)),\forall k\in\mathbb N$。第 3 节中给出了严格的定义。

这是因为：

引理 2.1.1 $\forall a,b\in\mathbb Z$，$a$ 是 $b$ 的整倍数，若 $b\equiv1\pmod p$，则$\dfrac ab\equiv a\pmod p$。

证明：设 $a=tb,\ b=sp+1$。则 $\dfrac ab\equiv t\equiv tsp+t\equiv a\pmod p$。

引理 2.1.2 $\forall a,b\in\mathbb Z$，$a$ 是 $b$ 的整倍数，$p$ 是素数且 $(p,b)=1$，则 $\dfrac ab\equiv ab^{p-2}\pmod p$。

证明：由费马小定理得 $b^{p-1}\equiv1\pmod p$。故 $\dfrac ab=\dfrac{ab^{p-2}}{b^{p-1}}$。由 引理 2.1.2 得 $\dfrac{ab^{p-2}}{b^{p-1}}\equiv ab^{p-2}\pmod p$。

则由引理 2.1.2 得 $\displaystyle\binom ni\operatorname{mod}n=\frac{n(n-1)\cdots(n-i+1)}{i!}\operatorname{mod}n=n(n-1)\cdots(n-i+1)\cdot(i!)^{n-2}\operatorname{mod}n=0$。

设 $n=tq^k$ 其中 $q\nmid t$，则 $\displaystyle\binom nq=\frac{n(n-1)\cdots(n-q+1)}{q!}=tq^{k-1}\frac{(n-1)\cdots(n-q+1)}{(q-1)!}=tq^{k-1}\binom {n-1}{q-1}$。由 引理 2.1.2 知，$\displaystyle\binom{n-1}{q-1}\equiv\big((n-1)\cdots(n-q+1)\big)\big((q-1)!\big)^{q-2}\pmod q$，而右侧两个因子都不整除于 $q$（前者不含 $q$ 的整倍数，后者都小于 $q$）。所以 $\displaystyle q\nmid\binom{n-1}{q-1}$。所以 $q\nmid t\displaystyle\binom{n-1}{q-1}$。所以 $q^k\nmid\displaystyle\binom nq$。

由于 $a$ 和 $n$ 互素，故 $a$ 和 $q^k$ 也互素。进而 $a^{n-q}$ 和 $q^k$ 也互素。

这里要证明多项式 $((X+a)^n-(X^n+a))$ 的 $X^q$ 项系数不整除于 $n$，从而证明同余式不成立。已知这一项的系数为 $\binom nqa^{n-q}$，刚刚证明了 $\binom nq$ 不整除于 $n$；又因为 $n,a$ 互素，所以 $a^{n-q}$ 也不整除于 $n$。由于这两者互素，所以它们的乘积——即整个系数也不整除于 $n$。

这里 $\operatorname{mod} X^r-1,n$ 的含义是这样的（在第 3 节中给出了严格的定义，这里只是形象的解释）：

1. $\operatorname{mod} n$ 是指对同余式两侧的多项式的每一个系数取关于 $n$ 的模，两侧各得到一个多项式，但其次数不变；
2. $\operatorname{mod} X^r-1$ 是指对同余式两侧的多项式做带余除法。比如左侧多项式为 $f(x)$，则找到 $\partial(r(x))<\partial(f(x))$ 满足 $f(x)=p(x)g(x)+r(x)$，$r(x)$ 即为左侧的“余数”。对右侧做一样的操作，如果两侧带余除法得到的 $r(x)$ 相同，则同余式成立。

可以验证，带余除法的“除数”为 $X^r-1$ 时，实际上是简单地将 $a_iX^i$ 这一项运算到 $a_iX^{i\operatorname{mod}r}$，也就是在指数层面上做模运算，消除了大于等于 $r$ 的项。运算完成后，对于 $\forall 0\leqslant i<r$，$X^i$ 项的系数即为 $\displaystyle\sum_{j\equiv i\pmod r}a_j$。

求和运算不影响模运算的结果。所以后文说，由 $(1)$ 式可以推出对于任意的 $r$，$(2)$ 式都成立。

这里：

• $\mathbb F[X]$ 指多项式环，其中元素具有形式 $a_nX^n+\cdots+a_1X_1+a_0$，其中 $a_i\in\mathbb F$。
• 有限域的阶就是其元素个数。
• $/$ 是商环的记号。这里，商环的构造是由 $h(X)$ 的同余关系导出的。

这里 $\operatorname{poly}(f(n))$ 指以 $f(n)$ 为变元的多项式。

引理 3.0.1 若 $x\equiv1\pmod r$，则对于 $\forall n\in\mathbb N$，$x^n\equiv1\pmod r$。

证明：设 $x=pr+1$，$p\in\mathbb Z$。则

$$(pr+1)^n=\sum_{i=0}^n\binom ni(pr)^i$$

对于 $\forall i>0$，显然 $r\mid(pr)^i$，此时 $\binom ni(pr)^i$ 这些项都整除 $r$。当 $i=0$ 时，$\binom ni(pr)^i=1$。所以 $x^n=(pr+1)^n\equiv1\pmod r$。

引理 3.0.2（费马-欧拉定理） $a^{\varphi(r)}\equiv1\pmod{r}$ 对任意满足 $(a,r)=1$ 的 $a$ 和 $r$ 成立。

证明：设 $x_1,x_2,\cdots,x_{\varphi(r)}$ 为小于 $r$ 的与 $r$ 互素的正整数。考虑集合 $\{ax_1,\cdots, ax_{\varphi(r)}\}$，其满足如下性质：

• 每个元素关于 $r$ 的模互不相等。否则，$\exists i,j$ 使得 $ax_i\equiv ax_j\pmod r$，则 $r\mid(ax_i-ax_j)$；另一方面由 $a,r$ 互素、$|x_i-x_j|<r$ 得到 $r\nmid a(x_i-x_j)$，矛盾。
• $(ax_i\operatorname{mod}r,r)=1$ 对于 $\forall i$ 成立。这可由最大公约数的积性得出：$(a,r)=1\wedge(x_i,r)=1\rArr(ax_i,r)=1\rArr(ax_i\operatorname{mod}r,r)=1$。

从而 $\{ax_i\operatorname{mod}r\mid 1\leqslant i\leqslant\varphi(i)\}$ 是小于 $r$ 且与 $r$ 互质的正整数。这和 $\{x_1,x_2,\cdots,x_{\varphi(r)}\}$ 的定义相同，这两个集合相等。从而

$$ax_1\cdot ax_2\cdots ax_{\varphi(r)}\equiv x_1\cdot x_2\cdots ax_{\varphi(r)}\pmod r$$

显然 $x_1x_2\cdots x_{\varphi(r)}$ 与 $r$ 互素，可以消去，于是得到：

$$a^{\varphi(r)}\equiv1\pmod r$$

证明：设 $\varphi(n)=k\mathrm o_r(a)+p$，$k\in\mathbb Z,1<p<n$。则 $a^{\varphi(n)}=(a^{\mathrm o_r(a)})^k\cdot a^p$。即 $a^p=\dfrac{a^{\varphi n}}{(a^{\mathrm o_r(a)})^k}$。由于 $a^{\mathrm o_r(a)}\equiv1\pmod r$，由引理 3.0.1 知 $(a^{\mathrm o_r(a)})^k\equiv1\pmod r$。再由引理 2.1.1 和引理3.0.2 知 $a^p\equiv a^{\varphi(r)}\equiv1\pmod r$。即 $p<\mathrm o_r(a)$ 也满足 $a^p\equiv1\pmod r$，与 $\mathrm o_r(a)$ 的定义矛盾。所以 $p=0$，$\mathrm o_r(a)\mid\varphi(r)$。

引理 3.1.1 函数

$$\tag{2.1}F(m,n)=\sum_{i=0}^{n-m}\frac{(-1)^i\binom{n-m}i}{m+i}$$

在 $m,n\in\mathbb N,1\leqslant m\leqslant n$ 上定义，则有恒等式

$$\tag{2.2}F(m,n)=\begin{cases}\dfrac1{m\binom nm},&m>0\\0,&m=0\end{cases}$$

证明：用数学归纳法对 $n-m$ 做归纳。 当 $n-m=0$ 时，$F(m,n)=0$ 是显然的。 假设 $n-m=r$ 时引理成立。考虑 $n-m=r+1$ 的情形：

$$\begin{aligned} F(m,n)&=F(m,m+r+1)\\ &=\sum_{i=0}^{r+1}\frac{(-1)^i\binom{r+1}i}{m+i}\\ &=\sum_{i=0}^{r+1}\frac{(-1)^i\left(\binom ri+\binom r {i-1}\right)}{m+i}\\ &=\sum_{i=0}^{r+1}\frac{(-1)^i\binom ri}{m+i}+\sum_{i=0}^{r+1}\frac{(-1)^i\binom r{i-1}}{m+i}\\ &=\sum_{i=0}^r\frac{(-1)^i\binom ri}{m+i}+\sum_{i=1}^r\frac{(-1)^i\binom r{i-1}}{m+i}\\ &=\sum_{i=0}^r\frac{(-1)^i\binom ri}{m+i}-\sum_{i=0}^r\frac{(-1)^i\binom ri}{m+i+1}\\ &=F(m,m+r)-F(m+1,m+1+r)\\ &=\frac1{m\binom{m+r}m}-\frac1{(m+1)\binom{m+r+1}{m+1}}\\ &=\frac{m!}{m\cdot(m+r)\cdots(r+1)}-\frac{(m+1)!}{(m+1)\cdot(m+r+1)\cdots(r+1)}\\ &=\frac{(m+1)!(r+1)}{m(m+1)\cdot(m+r+1)\cdots(r+1)}\\ &=\frac{m!}{m\cdot(m+r+1)\cdots(r+2)}\\ &=\frac1{m\binom{m+r+1}{m}} \end{aligned}$$

这就证明了等式 $(2.2)$ 的正确性。

证明：注意到引理 3.1.1 的式 $(2.1)$ 右侧分母只有 $m,(m+1),\cdots,n$，所以约分之后 $F(m,n)$ 的最简形式分母也只能是 $\{m,(m+1),\cdots,n\}$ 的子集的积。所以它必然整除 $\operatorname{LCM}(n)$。运用式 $(2.2)$ 即得：

$$\left.m\binom nm\middle|\operatorname{LCM}(n)\right.$$

由于 $\operatorname{LCM}(2n)\mid\operatorname{LCM}(2n+1)$，故有

$$\tag{2.3}\left.n\binom{2n}n\middle|\operatorname{LCM}(2n+1)\right.$$

又因为 $\displaystyle(2n+1)\binom{2n}n=(n+1)\binom{2n+1}{n+1}$，又有

$$\tag{2.4}\left.(2n+1)\binom{2n}n\middle|\operatorname{LCM}(2n+1)\right.$$

式 $(2.3)\ (2.4)$ 中 $(n,2n+1)=1$，所以

$$\left.n(2n+1)\binom{2n}n\middle|\operatorname{LCM}(2n+1)\right.$$

考虑 $(1+x)^{2n}$ 的二项式展开中，$\binom{2n}n$ 是最大的系数，故有不等式：

$$(1+x)^{2n}=\sum_{i=0}^{2n}\binom{2n}ix^i\leqslant\sum_{i=0}^{2n}\binom{2n}nx^i$$

两侧带入 $x=1$，得到：

$$2^{2n}\leqslant(2n+1)\cdot\binom{2n}n\cdot1$$

当 $n\geqslant4$ 时，

$$n(2n+1)\binom{2n}n\geqslant n\cdot2^{2n}\geqslant 2^{2n+2}$$

由于左侧整除 $\operatorname{LCM}(2n+1)$，所以 $n\geqslant4$ 时

$$\operatorname{LCM}(2n+2)\geqslant\operatorname{LCM}(2n+1)\geqslant n(2n+1)\binom{2n}n\geqslant 2^{2n+2}$$

即 $m\geqslant10$ 时，$\operatorname{LCM}(m)\geqslant 2^m$。可单独验证 $m=7,8,9$ 时不等式依然成立。

行 2 条件不满足的原因很明显：素数不可能是某个因子的高次幂。行 5 条件不满足的原因是，素数 $n$ 和任意比它小的数 $a$ 都互素，所以 $(a,n)=1$ 恒成立，条件不满足。

行 10 的条件就是引理 2.1 的否。当 $n$ 是素数时，同余式总是相等的。

这里反设法假设：$n$ 是合数，但算法执行到了行 8，也就是行 7 条件 $n\leqslant r$ 成立。那么，在行 5 的条件判断中，对于 $n$ 的任意一个非平凡因子 $a$，$(a,n)=a$ 满足 $1<(a,n)<n\leqslant r$ 的条件，所以算法只会执行到行 6。于是推出矛盾，得到结论：如果算法在行 8 返回 $\tt PRIME$，那么 $n$ 必是素数。

第一个不等式的细节：

$$\begin{aligned} &n^{\lfloor\log B\rfloor}\cdot\prod_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)\\ <&n^{\lfloor\log B\rfloor}\cdot\prod_{i=1}^{\lfloor\log^2n\rfloor}n^i\\ =&n^{\lfloor\log B\rfloor+\sum_{i=1}^{\lfloor\log^2n\rfloor}i}\\ \leqslant&n^{\lfloor\log B\rfloor+\frac12\lfloor\log^2n\rfloor\cdot(\lfloor\log^2n\rfloor+1)}\\ \end{aligned}$$

第二个不等式的细节：

$$x^4>\lfloor\log(\lceil x^5\rceil)\rfloor+\frac12\lfloor x^2\rfloor(\lfloor x^2\rfloor+1)$$

上式在 $n\geqslant4$ 时成立，而 $n=2,3$ 的情形也可验证原式成立。

第三个不等式是显然的。第四个不等式是取整符号的性质。

$s\leqslant B$ 的解释：这里使用反证法：否则 $s>B$，则由 $s$ 的定义，小于 $s$ 的所有正整数皆整除 $\displaystyle n^{\lfloor\log B\rfloor}\cdot\prod_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)$。所以它们的最小公倍数也有 $\left.\operatorname{LCM}(s)\middle|\displaystyle n^{\lfloor\log B\rfloor}\cdot\prod_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)\right.$，即 $\operatorname{LCM}(s)\leqslant\displaystyle n^{\lfloor\log B\rfloor}\cdot\prod_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)<2^B$。这与引理 3.1 矛盾。

“$s$ 中与 $n$ 互素的因子”的解释：这里形象地讲，求 $s$ 中与 $n$ 互素的因子是将 $n$ 的因子全部从 $s$ 中除去。而证明最初提到的 $k\leqslant\lfloor\log B\rfloor$ 以及现在 $s\leqslant B$ 限制了 $n$ 的因子重复的个数最多不超过 $\lfloor\log B\rfloor$ 个。所以 $s$ 中和 $n$ 相同因子的部分为 $(s,n^{\lfloor\log B\rfloor})$，用 $s$ 除以它即得到 $s$ 中互素的部分。

“$r$ 不整除”的解释：反设 $r\mid\displaystyle\prod_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)$，则 $r\mid n^{\lfloor\log B\rfloor}\cdot\displaystyle\prod_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)$。由于 $r,n^{\lfloor\log B\rfloor}$ 互素，且后者也整除这个数，所以 $rn^{\lfloor\log B\rfloor}$ 也整除这个数。但 $s$ 是 $rn^{\lfloor\log B\rfloor}$ 的因子，这与 $s$ 不整除矛盾。

上面证明了 $n^i\not\equiv1\pmod r$ 对于任意 $1\leqslant i\leqslant\lfloor\log^2n\rfloor$ 都成立。根据 $\mathrm o_r(n)$ 的定义，则 $\mathrm o_r(n)$ 必然大于 $\log^2n$。