用户: Rushcheyo/《算法分析与设计》论文阅读/PRIMES is in P

$\mathrm{P}\mathrm{R}\mathrm{I}\mathrm{M}\mathrm{E}\mathrm{S}$ 是指所有质数构成的集合. 本文旨在介绍 AKS 算法, 它是第一个多项式时间的确定性质数判定算法, 即输入 $n\in \mathbb{N}$ 在 $O(\mathrm{polylog}n)$ 时间内判断是否有 $n\in \mathrm{P}\mathrm{R}\mathrm{I}\mathrm{M}\mathrm{E}\mathrm{S}$.

本文中 $\log$ 以 $2$ 为底, $\ln$ 以 $e$ 为底.

1一个随机算法

先介绍一个由 Agrawal 和 Biswas 在 1999 年发表的比较简单的随机算法 [AB99], 这是之后确定性算法的基础. 我们使用的关键判据如下:

引理 1.1 (Fermat 小定理的推广). 令 $a\in \mathbb{Z},n\ge 2,(a,n)=1$, $n$ 是质数当且仅当:

$$(x+a{)}^n\equiv x^n+a(\mathrm{m}\mathrm{o}\mathrm{d}n)$$(1)

证明. 若 $n$ 是质数, $\left(\genfrac{}{}{0ex}{}{n}{i}\right)=\frac{n!}{i!(n-i)!}$ 一定是 $n$ 的倍数 (因为分子有素因子 $n$, 分母没有) ;

若 $n$ 不是质数, 任取质数 $p\mid n$, 令 $k$ 满足 $p^k\mid n$ 且 $p^{k+1}\nmid n$, 考察 (1) 式左边的 $x^{p^k}$ 项系数:

$$\begin{array}{rl}& \left(\genfrac{}{}{0ex}{}{n}{p^k}\right)a^{n-p^k}\\ \equiv & \frac{n\times (n-1)\times \cdots \left(n-p^k+1\right)}{(p^k)!}{a}^{n-p^k}\\ \equiv & \frac{n}{p^k}(-1{)}^{p^k-1}{a}^{n-p^k}\\ \not\equiv & 0(\mathrm{m}\mathrm{o}\mathrm{d}p)\end{array}$$

那么 $\mathrm{m}\mathrm{o}\mathrm{d}n$ 更不能是 0.

$\square$

然而该多项式恒等式的次数过高, 为降低检验复杂度, 我们取 $d=\lceil \log n\rceil$, 并随机选取 $d$ 次首一多项式 $r(x)=x^d+r_{d-1}{x}^{d-1}+\cdots +r_0$, 亦即 $r_0,\dots ,r_{d-1}$ 在 ${\mathbb{Z}}_n$ 中均匀独立随机, 之后判断是否有:

$$(x+1{)}^n\equiv x^n+1(\mathrm{m}\mathrm{o}\mathrm{d}(r(x),n))$$(2)

引理 1.2. 当 $n$ 不是质数且存在至少是 11 的质数 $p\mid n$ 时, (2) 式不成立的概率至少是 $\frac{1}{4d}$.

证明. 令 $Q(x):=(x+1{)}^n-x^n-1$. 在引理 1.1 的证明中我们已看见, 在 $\mathrm{GF}(p)$ 中 $Q(x)\ne 0$, 那么 $Q(x)$ 可以唯一分解, 且各不可约因子中度数为 $d$ 的不超过 $n/d$ 个.

$Q(x)$ 的随机方式使 $Q(x)\mathrm{m}\mathrm{o}\mathrm{d}p$ 的系数在 $\mathrm{GF}(p)$ 中随机选取. 考虑到 $P(\text{(2) 式不成立})\ge P(\text{r(x) 不可约且 (2) 式不成立})=P(\text{r(x) 不可约})-P(\text{r(x) 是 Q(x) 的不可约因子})=P(\text{r(x) 不可约})-\frac{n}{d{p}^d}$, 只要估计 $\mathrm{GF}(p)$ 里 $d$ 次首一不可约多项式的数目. 由 Möbius 反演熟知这是:

$$\begin{array}{rl}& \frac{1}{d}\sum _{e|d}\mu (e)p^{d/e}\\ \ge & \frac{1}{d}\left(p^d-\sum _{e<n,e|d}{p}^{d/e}\right)\\ \ge & \frac{p^d}{d}-p^{d/2}\end{array}$$

代入概率下界:

$$\frac{1}{d}-\frac{1}{p^{d/2}}-\frac{n}{d{p}^d}\ge \frac{1}{2d}-\frac{n}{d{p}^d}\ge \frac{1}{4d}$$$\square$

分析一下时间复杂度: (2) 式计算需要 $O(\log n)$ 次 $d=O(\log n)$ 次多项式乘法和取余, 用 FFT 每次需要 $\tilde{O}(\log n)$ 次 $O(\log n)$ 位整数乘法 (也是 $\tilde{O}(\log n)$ 时间) , 总共是 $\tilde{O}\left({\log }^{4}n\right)$ 时间, 重复 $\tilde{O}(\log n)$ 次后即可达到 $\frac{1}{\log n}$ 的错误率, 因此该算法共消耗 $\tilde{O}\left({\log }^{5}n\right)$ 时间.

2去随机化

在上面的算法中, 我们随机选取了一个多项式, 而从分析中可以看出, 我们其实只是想要一个次数比较大的不可约多项式. 另一方面还可以观察到, 我们检查 $\mathrm{m}\mathrm{o}\mathrm{d}(r(x),n)$ 下是否成立, 间接的检查了对素元 $h(x)|r(x)$ 和 $p|n$ 是否在 $\mathrm{m}\mathrm{o}\mathrm{d}(h(x),p)$ 下成立.

在 AKS 算法中, 我们将该多项式固定为 $x^r-1$. 在 $\mathbb{Q}$ 上, 我们知道 $x^r-1$ 有一个次数是 $\phi (r)$ 的不可约因子: 第 $r$ 个分圆多项式 $Q_r(x)$. 然而在 $\mathrm{GF}(p)$ 上情况有所不同:

引理 2.1 (有限域上的分圆多项式). 设 $F_q$ 是 $q$ 阶有限域, $(r,q)=1$, $Q_r(x)$ 在 $F_q[x]$ 上的每个不可约因子的次数均为 ${\mathrm{ord}}_r(q)$. 这里 ${\mathrm{ord}}_r(q)$ 表示 $q$ 模 $r$ 的阶.

证明. 取 $F_q$ 的代数闭包 $K$. 对 $F_q$ 有刻画: 对 $x\in K$, $x\in F_q$ 当且仅当 $x^q-x=0$.

考虑 $r$ 次本原根 $\omega$ (即 $x^r-1$ 的 $r$ 个根中不是 $d<r$ 次单位根的这些组成的乘法群 (域的乘法群的有限子群必为循环群) 的生成元, 分圆多项式的定义也是一样的) , 我们断言其极小多项式是 $(x-\omega )(x-{\omega }^q)\cdots \left(x-{\omega }^{q^{{\mathrm{ord}}_r(q)-1}}\right)$, 这是由于:

1.	$x\mapsto x^q$ 是 $K$ 上只固定 $F_q$ 的自同构, 于是一个 $F_q$ 上多项式零点包含 $\omega$ 就要包含 ${\omega }^q$;
2.	该多项式的系数 $q$ 次方后不变 (因为是根的初等对称多项式, 其 $q$ 次方是根 $q$ 次方亦即轮换后的初等对称多项式, 由对称性不变) , 因而在 $F_q$ 中.

其实以上无非是说, 对于 Galois 扩张 $E/F$, $\alpha$ 的最小多项式就是 ${\prod }_{\sigma \in \mathrm{Gal}(E/F)}(x-\sigma (\alpha ))$. 而 $F_q$ 的有限扩张的 Galois 群由 $x\mapsto x^q$ 生成, 这是由于自同构必须是 $x\mapsto x^k$ (因为扩域的乘法群循环) , 然后这个固定底域当且仅当 $q|k$.

$\square$

因此, 取 $h(x)$ 是引理 2.1 中这样一个不可约因子, 那么我们的分析可以限制在域 $\mathrm{GF}(p)[x]/(h(x))$ 上. 为了保证 $h(x)$ 的次数够大, 我们 $r$ 的选取如下:

引理 2.2. 对 $n\ge 2$, 存在 $2\le r\le \lceil {\log }^{5}n+\log n\rceil +2$ 且 $(r,n)=1$, 使得 ${\mathrm{ord}}_r(n)>{\log }^{2}n$.

证明.

反证这些 $r$ 都满足 ${\mathrm{ord}}_r(n)\le {\log }^{2}n$, 则它们均整除:

$$\prod _{i=1}^{\lfloor {\log }^{2}n\rfloor }(n^i-1)<n^{{\log }^{4}n}=2^{{\log }^{5}n}$$

因此该范围内与 $n$ 互质的数的 $\mathrm{lcm}$ 至多是 $2^{{\log }^{5}n}$, 从而该范围内所有数的 $\mathrm{lcm}$ 至多是 $2^{{\log }^{5}n+\log n}$.

下面只需要证明 $\forall k\ge 2,\mathrm{lcm}(1,2,\dots ,k)\ge 2^{k-2}$ 就导出了矛盾.

首先证明 $\mathrm{lcm}\left(\left(\genfrac{}{}{0ex}{}{k}{0}\right),\left(\genfrac{}{}{0ex}{}{k}{1}\right),\cdots ,\left(\genfrac{}{}{0ex}{}{k}{k}\right)\right)|\mathrm{lcm}(1,2,\dots ,k)$. 由 Kummer 定理, 对任意质数 $p$, $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ 中 $p$ 的次数是 $i$ 和 $k-i$ 在 $p\le n$ 进制下相加的进位次数, 显然不超过 $n$ 的位数减一, 即 $\lfloor {\log }_{p}n\rfloor$, 这就是 $p$ 在 $\mathrm{lcm}(1,2,\dots ,k)$ 中的次数.

然后考虑 $\mathrm{lcm}\left(\left(\genfrac{}{}{0ex}{}{k}{k/2}\right),\left(\genfrac{}{}{0ex}{}{k}{k/2-1}\right)\right)$. 我们知道 $\left(\genfrac{}{}{0ex}{}{k}{k/2}\right)=\left(\genfrac{}{}{0ex}{}{k}{k/2-1}\right)\frac{k-k/2+1}{k/2}$. 若 $k$ 是偶数, $k/2$ 与 $k-k/2+1$ 互质, 则 $k/2\mid \left(\genfrac{}{}{0ex}{}{k}{k/2-1}\right)$, 易知该 $\mathrm{lcm}$ 是 $\left(\genfrac{}{}{0ex}{}{k}{k/2}\right)k/2\ge 2^{k-1}$. 当 $k$ 是奇数时, $\mathrm{lcm}(1,2,\dots ,k)\ge \mathrm{lcm}(1,2,\dots ,k-1)\ge 2^{k-2}$.

$\square$

引理 2.2 中, 我们只保证了 ${\mathrm{ord}}_r(n)$, 但是 $h(x)$ 的次数是 ${\mathrm{ord}}_r(p)$. 在 Agrawal, Kayal 和 Saxena 的第一版预印本里, 他们确实用了解析数论的工具做到了这一点, 然而 Hendrik Lenstra 简化了证明使得我们只需保证 ${\mathrm{ord}}_r(n)$ 够大.

下面给出详细的算法:

1.	如果 $n=a^b(a\ge 1,b>1)$, 拒绝;
2.	找最小的 $r$ 满足 $(r,n)=1$ 且 ${\mathrm{ord}}_r(n)>{\log }^{2}n$;
3.	如果存在 $a\le r$ 使得 $1<(a,n)<n$, 拒绝;
4.	如果 $n\le r$, 接受;
5.	对 $1\le a\le l:=\lfloor \sqrt{\phi (r)}\log n\rfloor$ 检查: $$(x+a{)}^n\equiv x^n+a(\mathrm{m}\mathrm{o}\mathrm{d}(x^r-1,n))$$(3) 不成立则拒绝; 全部成立则接受.

3算法的分析

如同上一节所说, 我们现在固定质因子 $p|n$ 和 $x^r-1$ 的次数为 ${\mathrm{ord}}_r(p)$ 的不可约因子 $h(x)$, 以及由他们诱导的域 $F:=\mathrm{GF}(p)[x]/((h(x))$. 由于算法第 3、4 步的检查, 必有 $p>r$ 且 $(r,p)=1$.

我们有 $(x+a{)}^n\equiv x^n+a(x^r-1,p)$ 对 $1\le a\le l$ 成立. 另一方面, 我们自然有 $(x+a{)}^p\equiv x^p+a(\mathrm{m}\mathrm{o}\mathrm{d}(x^r-1,p))$. 在该式两边取 $n/p$ 次方, 得到 $(x^p+a{)}^{n/p}\equiv x^n+a(\mathrm{m}\mathrm{o}\mathrm{d}(x^r-1,p))$.

展开上面式子, 有 $\forall 1\le t<r$, ${\sum }_{pi\mathrm{m}\mathrm{o}\mathrm{d}r=t}\left(\genfrac{}{}{0ex}{}{n/p}{i}\right)a^{n/p-i}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$, 由于 $(p,r)=1$, 这相当于 ${\sum }_{i\mathrm{m}\mathrm{o}\mathrm{d}r=t}\left(\genfrac{}{}{0ex}{}{n/p}{i}\right)a^{n/p-i}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$, 因而结合 $a^{n/p}\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$, $(x+a{)}^{n/p}\equiv x^{n/p}+a(\mathrm{m}\mathrm{o}\mathrm{d}(x^r-1,p))$. 我们抽象出如下性质:

定义 3.1. 如果 $m$ 和多项式 $f$ 满足 $f(x^m)\equiv f^m(x)(\mathrm{m}\mathrm{o}\mathrm{d}(x^r-1,p))$, 称 $m$ 对 $f$ 是内省的 (英文: introspective) .

引理 3.2 (数乘封闭性). 如果 $m_1$ 和 $m_2$ 都对 $f$ 内省, $m_1{m}_2$ 对 $f$ 内省.

证明. $f(x^{m_1{m}_2})={\left(f(x^{m_1})\right)}^{m_2}={\left(f^{m_1}(x)\right)}^{m_2}=f^{m_1{m}_2}(x)$, 其中第一个等号在 $\mathrm{m}\mathrm{o}\mathrm{d}(x^{m_{1}r}-1,p)$ 意义下, 然而这比 $\mathrm{m}\mathrm{o}\mathrm{d}(x^r-1,p)$ 要强, 因为 $(x^r-1)\mid (x^{m_{1}r}-1)$.

$\square$

引理 3.3 (多项式乘封闭性). 如果 $m$ 对 $f_1$ 和 $f_2$ 均内省, 则 $m$ 对 $f_1{f}_2$ 内省.

证明. 显然.

$\square$

定义 $I:=\left\{{\left(\frac{n}{p}\right)}^i{p}^j:i,j\ge 0\right\}$, $P:=\left\{{\prod }_{a=0}^l(x+a{)}^{e_a}:e_a\ge 0\right\}$, 立刻有:

推论 3.4.

$\forall m\in I,\forall f\in P$, $m$ 对 $f$ 内省.

现在我们回到域 $F$ 上. $P$ 自然对应由 $(x+a)(0\le a\le l)$ 生成的群 (因为每个元素都有阶) $\mathcal{G}$, 由有限域性质这是个循环群. 下面会分别给出 $|\mathcal{G}|$ 的上界和下界导出矛盾.

我们注意到集合 $I$ 的结构高度取决于 $n$ 是否是 $p$ 的幂次. 下面将 $I$ 和 $\mathcal{G}$ 联系在一起.

引理 3.5. 若 $a,b\in I$ 且 $r\mid (a-b)$, 则 $|\mathcal{G}|\mid (a-b)$.

证明. 此时 $\forall g\in \mathcal{G}$, $g(x^a)=g(x^b)$, 因而 $g^a=g^b$, 故 $g^{a-b}=1$. 取 $g$ 为生成元立得.

$\square$

上面的引理提示我们定义群 $G$ 由 $n$ 和 $p$ 在 ${\mathbb{Z}}_r$ 上生成 (记得 $(n,r)=1$) , 于是我们可以估计 $|\mathcal{G}|$:

引理 3.6. 若 $n$ 不是 $p$ 的幂次, 则 $|\mathcal{G}|\le n^{\lfloor \sqrt{|G|}\rfloor }$.

证明. 对 $0\le i,j\le \lfloor \sqrt{|G|}\rfloor$, 必有两个 ${\left(\frac{n}{p}\right)}^i{p}^j$ 模 $r$ 相同的, 由引理 3.5 $|\mathcal{G}|$ 不超过他们中的较大值, 更不超过 $n^{\lfloor \sqrt{|G|}\rfloor }$.

$\square$

为了导出矛盾, 我们只需要给出 $|\mathcal{G}|$ 的下界. 如果两个多项式度数小于 $h(x)$ 的度数, 它们对 $h(x)$ 取模后自然不同, 因此 $|\mathcal{G}|\ge \left(\genfrac{}{}{0ex}{}{l+\mathrm{deg}h}{\mathrm{deg}h-1}\right)$ (这是不定方程 $\sum e_a-1<\mathrm{deg}h$ 的解数) 是显然的 (注意易证 $\mathrm{deg}h>1$ 去保证 $x+a\ne 0$) . 然而我们在第二节末尾讨论过, 我们能方便控制的是 ${\mathrm{ord}}_r(n)$, 因此我们需要下面更强的下界:

引理 3.7 (Hendrik Lenstra). $|\mathcal{G}|\ge \left(\genfrac{}{}{0ex}{}{l+|G|}{|G|-1}\right)$

证明. 同样, 我们证明两个 $P$ 中度数均小于 $|G|$ 的不同多项式 $f$ 和 $g$ 在 $\mathrm{m}\mathrm{o}\mathrm{d}h(x)$ 后仍然不同. 反证相同. 记 $p=f-g$, 有 $\mathrm{deg}p<|G|$. $\forall m\in I$, $p(x^m)\equiv f(x^m)-g(x^m)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}(h(x),p))$. 注意 $h(x)$ 是 $r$ 次本原单位根的极小多项式, 于是 $x$ 是域 $F$ 上的 $r$ 次本原单位根. 由于 $(m,r)=1$, $x^m$ 也都是 $r$ 次本原单位根. $p$ 因而作为域 $\mathbf{F}$ 上的系数非 0 多项式有 $|G|$ 个不同零点, 矛盾.

$\square$

定理 3.8. AKS 算法是正确的.

证明. 现在只需要证 $\left(\genfrac{}{}{0ex}{}{l+|G|}{|G|-1}\right)>n^{\lfloor \sqrt{|G|}\rfloor }$, 因为算法第一步就拒绝了次幂数, 最后只能 $n$ 是质数.

显然 $|G|\le \phi (r)$, 故 $l\ge \lfloor \sqrt{|G|}\log n\rfloor$.

$$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{l+|G|}{|G|-1}\right)& \ge \left(\genfrac{}{}{0ex}{}{|G|+\lfloor \sqrt{|G|}\log n\rfloor }{|G|-1}\right)\\ & =\left(\genfrac{}{}{0ex}{}{|G|+\lfloor \sqrt{|G|}\log n\rfloor }{\lfloor \sqrt{|G|}\log n\rfloor +1}\right)\end{array}$$

显然 $|G|\ge {\mathrm{ord}}_r(n)>{\log }^{2}n$, 于是 $|G|>\lfloor \sqrt{|G|}\log n\rfloor$.

$$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{|G|+\lfloor \sqrt{|G|}\log n\rfloor }{\lfloor \sqrt{|G|}\log n\rfloor +1}\right)& \ge \left(\genfrac{}{}{0ex}{}{2\lfloor \sqrt{|G|}\log n\rfloor +1}{\lfloor \sqrt{|G|}\log n\rfloor +1}\right)\\ & \ge \frac{2^{2\lfloor \sqrt{|G|}\log n\rfloor }-1}{\lfloor \sqrt{|G|}\log n\rfloor }\\ & >2^{\lfloor \sqrt{|G|}\log n\rfloor +1}\\ & \ge n^{\sqrt{|G|}}\\ & \ge n^{\lfloor \sqrt{|G|}\rfloor }\end{array}$$

$\square$

最后分析 AKS 算法的时间复杂度. 由于 $r=O\left({\log }^{5}n\right)$, 第 5 步要执行 $O\left({\log }^{3.5}n\right)$ 步, 每步进行 $O(\log n)$ 次乘法, 每次乘法进行 $\tilde{O}\left({\log }^{5}n\right)$ 次 $O(\log n)$ 位数乘, 因此总的时间复杂度是 $\tilde{O}\left({\log }^{10.5}n\right)$.

参考文献

[AB99]	M. Agrawal and S. Biswas (1999). Primality and identity testing via Chinese remaindering. Proceedings of IEEE FOCS 1999, pp. 202–209.
[AKS02]	M. Agrawal, N. Kayal and N. Saxena (2004). PRIMES is in P. Annals of Mathematics 160, pp. 781–793.