文章: Agrawal M, Kayal N, Saxena N. PRIMES Is in P[J]. Annals of Mathematics, 2004, 160(2):781-793.
文章分为正确性和复杂度两部分:
- 正确性: 素数显然会返回
PRIME, 只需证返回PRIME的是素数. 返回素数的地方只有Step 2和Step 6, 分别讨论之.Step 4: 若 \(n\) 是合数则会在Step 3中返回, 矛盾.Step 6: 分段考虑.- 先考虑
Step 2中 \(r\) 的范围, 可得 \(r\leqslant\lceil\log^5n\rceil\). - 定义多项式之间的关系introspective: \([f(x)]^m=f(x^m)~({\rm mod}~x^r-1,p)\), 则该性质对 \(m\) 和 \(f\) 都满乘积性质.
- 由于在
Step 5没有返回COMPOSITE, 故 \(\frac{n}{p},p\) 对 \(x+a\) 是introspective的. 故 \(\frac{n}{p}\) 与 \(p^j\) 的任意乘积对 \(x+a~(0\leqslant a\leqslant l)\) 的任意乘积是introspective的. - 进一步, 通过建立两个群 \(G\) 和 \(\mathcal{G}\), 可得到 \(|\mathcal{G}|\) 的下界和一个由条件的上界. 并可最终得到 \(n=p\), 即 \(n\) 是素数.
- 先考虑
- 至此算法正确性得证.
- 复杂度: 逐步分析可知
Step 5复杂度最高, 为 \(O^\sim(\log^\frac{21}{2}n)\).
记号说明和准备工作
记号列表
文中出现的记号记录如下:
- \(P\): 图灵机在多项式时间内可以解决的问题;
- \(F_p\) 表示阶为 \(p\) 的有限域, 其中 \(p\) 是素数;
- \(f(x)=g(x)~({\rm mod}~h(x),n)\): 表示 \(f(x)=g(x)\) 在 \(\mathbb{Z}_n[x]/\langle h(x)\rangle\) 中成立;
- \(O^\sim (t(n))\): 表示 \(O(t(n))\cdot {\rm poly}(\log t(n))\). 其中 \(\log\) 表示以 \(2\) 为底的对数;
- \(o_r(a)\): 表示 \(a\) 模 \(r\) 的指数. 即最小的 \(k\), s.t. \(a^k=1~({\rm mod}~r)\).
为不影响思路的连贯性, 长一点的证明细节都补在最后.
准备工作
LEMMA 1. 设 \(a\in\mathbb{Z}\), \(n\geqslant 2\in\mathbb{N}\), 且 \((a,n)=1\), 则 \(n\) 是素数当且仅当 \[(x+a)^n=x^n+a~({\rm mod~n}).\] Proof. 直接讨论, 利用二项式系数的性质即可.
PRELIMINARY 1. 若 \(h(x)\) 是 \(F_p[x]\) 中的 \(d\) 次不可约多项式, 则 \(F_p[x]/\langle h[x]\rangle\) 是阶为 \(p^d\) 的有限域.
Proof. 设 \(F(\alpha)=0\), 考虑映射 \(\varphi:~F[\alpha]\to F[x],~f(\alpha)\mapsto f(x)\), 则由环同态基本定理可得 \[F(\alpha)=F[\alpha]\simeq F[x]/\langle p(x)\rangle.\] 由此即可证得结论.
PRELIMINARY 2. 对于 \(\forall a,r\in\mathbb{N}\) 满足 \((a,r)=1\), 都有 \(o_r(a)~\vert~\phi(r)\).
Proof. 若不满足上式, 与 \(o_r(a)\) 的最小性矛盾.
LEMMA 2. 令 \({\rm LCM}(n)\) 表示前 \(n\) 个数的lcm, 则对 \(n\geqslant 7\) 有: \({\rm LCM}(n)\geqslant 2^n\).
Proof. Nair M. On Chebyshev-type inequalities for primes[J]. American Mathematical Monthly, 1982, 89(2):126-129.
算法正确性
需要证明以下两条:
- \(n\) 是素数\(\to\)算法返回
PRIME; - 算法返回
PRIME\(\to\)\(n\) 是素数.
事实上第一条是显然的, 主要部分是第二条的证明.
\(n\) 是素数\(\to\)算法返回 PRIME
LEMMA 3. 若 \(n\) 是素数, 则算法返回
PRIME.
Proof. 这一条其实是很显然的. 证明全是废话, 略掉.
算法返回 PRIME \(\to n\) 是素数
算法返回 PRIME 的地方只有两处, 分别为 Step 4 和 Step 6. 以下分别讨论之.
Step 4 返回 PRIME \(\to n\) 是素数
证明很容易: 如果 \(n\) 是合数且 \(n\leqslant r\), 则在Step3 中一定可找到 \(n\) 的一个非平凡因子. 故在 Step 3 一定会返回 COMPOSITE, 矛盾! 故 Step 4 返回 PRIME \(\Rightarrow n\) 是素数.
Step 6 返回 PRIME \(\to n\) 是素数
算法的核心步骤是 Step 2 和 Step 5. 算法在 Step 2 中取了一个 \(r\) 值, 所以我们从 \(r\) 的大致取值开始考虑.
LEMMA 4. \(\exists r\leqslant\max\{3,\lceil\log^5 n\rceil\}\), s.t. \(o_r(n)>\log^2n\).
Proof. 单独讨论 \(n=2\) 情况, 即可设 \(n>2\), 此时可利用 LEMMA 2 进行证明.
由于 \(o_r(n)>1\), 故存在 \(n\) 的素因子 \(p\), s.t. \(o_r(p)>1\) (否则容易得到 \(o_r(n)=1\), 矛盾). 进一步应有 \(p>r\), 否则在 Step 3 和 Step 4 就已经判断了 \(n\) 的素性. 又由于 \((n,r)=1\)(否则在 Step 3 和 Step 4 会判定 \(n\) 素性), 故 \(p,n\in\mathbb{Z}_r^*\). \(p\) 和 \(r\) 在后文中将被固定, 再令 \(l=\lfloor\sqrt{\phi(r)}\log n\rfloor\).
由于算法执行到了 Step 6, 故在 Step 5 没有返回 COMPOSITE. 即: \[(x+a)^n=x^n+a~({\rm mod}~x^r-1,n)\quad\forall a,0\leqslant a\leqslant l.\] 于是 \[(x+a)^n=x^n+a~({\rm mod}~x^r-1,p)\quad\forall a,0\leqslant a\leqslant l.\] 由以上两式可得: \[(x+a)^\frac{n}{p}=x^\frac{n}{p}+a~({\rm mod}~x^r-1,p)\quad\forall a,0\leqslant a\leqslant l.\] 结合 LEMMA 1, 此时的 \(n\) 和 \(\frac{n}{p}\) 都满足 LEMMA 1 的条件, 将该性质定义如下:
DEFINITION 1. 对于多项式 \(f(x)\) 和 \(m\in\mathbb{N}\), 称 \(m\) 是instropective的, 如果 \[[f(x)]^m=f(x^m)~({\rm mod}~x^r-1,p).\]
很容易证明instropective有如下性质:
LEMMA 5. 若 \(m\) 和 \(m'\) 对 \(f(x)\) 都是instropective的, 则 \(m\cdot m'\) 对 \(f(x)\) 也是instropective的.
LEMMA 6. 若 \(m\) 对 \(f(x)\) 和 \(g(x)\) 都是instropective的, 则 \(m\) 对 \(f(x)\cdot g(x)\) 也是instropective的.
于是可以得到如下事实:
- 由前文的三个等式可知 \(\frac{n}{p}\) 和 \(p\) 对 \(x+a\) 是instropective的, \(\forall 0\leqslant a\leqslant l\).
- 进一步, 集合 \(I=\{(\frac{n}{p})^i\cdot p^j~\vert~ i,j>0\}\) 中的每个数对集合 \(P=\{\prod\limits_{a=0}^l(x+a)^{e_a}~\vert~ e_a\geqslant 0\}\) 中的每个多项式都是introspective的.
进一步可在上述集合的基础上如下定义两个群:
- \(G\): \(I\) 中所有的数模 \(r\) 的余数构成一个群. 设 \(\vert G\vert=t\).
- 显然 \(G\subset \mathbb{Z}_r^*\)(生成元都在 \(\mathbb{Z}_r^*\) 中).
- 由 \(o_r(n)>\log^2n\) 可知, \(t>\log^2n\).
- \(\mathcal{G}\): 由 \(x,x+1,\cdots,x+l\) 在域 \(F=F_p[x]/\langle h(x)\rangle\) 中生成的群.
- 显然 \(\mathcal{G}\) 是 \(F\) 乘法群的子群.
- \(P\) 中所有多项式在模 \(h(x)\) 和 \(p\) 的意义下关于乘法构成一个群.
\(\vert\mathcal{G}\vert\) 的范围由如下引理给出(证明细节见后文):
LEMMA 7. 下界: (Hendrik Lenstra Jr.) \(\vert\mathcal{G}\vert\geqslant\binom{t+l}{t-1}\).
LEMMA 8. 上界: 若 \(n\) 不是 \(p\) 的方幂, 则 \(\vert\mathcal{G}\vert\leqslant n^{\sqrt{t}}\).
进一步即可得到最终的结果:
LEMMA 9. 若算法返回
PRIME, 则 \(n\) 是素数.
Proof. 由 LEMMA 7, 有: \[ \begin{align} \vert\mathcal{G}\vert &\geqslant \binom{t+l}{t-1} & \\ &\geqslant \binom{l+1+\lfloor\sqrt{t}\log n\rfloor}{\lfloor\sqrt{t}\log n\rfloor} &\quad (由于~t>\sqrt{t}\log n) \\ &\geqslant \binom{2\lfloor\sqrt{t}\log n\rfloor+1}{\lfloor\sqrt{t}\log n\rfloor} &\quad (由于~l\geqslant \lfloor\sqrt{t}\log n\rfloor) \\ &\geqslant 2^{\lfloor\sqrt{t}\log n\rfloor+1} &\quad (由于~\lfloor\sqrt{t}\log n\rfloor>\lfloor\log^2n\rfloor\geqslant 1) \\ &\geqslant n^{\sqrt{t}}. \end{align} \] 由 LEMMA 8, 当 \(n\) 不是 \(p\) 的方幂时, 有\(\vert\mathcal{G}\vert\leqslant n^\sqrt{t}\). 故 \(\exists k\), s.t. \(n=p^k\). 若 \(k>1\), 则在Step 1就会返回COMPOSITE. 故只有 \(k=1\), 即 \(n=p\), 即 \(n\) 为素数.
至此, 算法正确性已经证明完毕. 可归纳为如下定理:
THEOREM 1. 算法返回
PRIME当且仅当 \(n\) 是素数.
复杂度证明
首先做如下假定:
- \(m\) 位数的四则运算耗时均为 \(O^\sim(m)\);
- 两个系数为 \(m\) 位整数的 \(d\) 次多项式的四则运算耗时为 \(O^\sim(d\cdot m)\).
- \(n\) 的位数大致为 \(O(\log n)\).
对于算法的复杂度, 我们将证明如下定理:
THEOREM 2. 算法的渐进时间复杂度为 \(O^\sim(\log^{\frac{21}{2}}n)\).
Proof. 按照算法步骤逐个讨论:
Step 1: 判断是否整数的幂.
时间复杂度 \(O^\sim(\log^3n)\), 参见 Mordern Computer Algebra. Cambridge Univ.;
Step 2: 求一个 \(r\), s.t. \(o_r(n)>\log^2n\).
1. 取 \(r\), s.t. \(o_r(n)>\log^2n\). 只需枚举 \(k\leqslant\log^2n\), 故至多需要 \(O(\log^2n)\).
2. 取定一个 \(r\) 后, 至多进行 \(O(\log^2n)\) 次模 \(r\) 乘法, 开销至多 \(O^\sim(\log^2n\log r)\).
3. 由 LEMMA 4, 至多需要测试 \(O(\log^5n)\) 个不同的 \(r\).
综上,Step 2复杂度至多 \(O^\sim(\log^7n)\).
Step 3: 需要求 \(r\) 次gcd.
1. 每次 gcd 的开销为 \(O(\log n)\).
2. \(r\) 的开销为 \(O(\log^5n)\).
综上,Step 3的复杂度为 \(O(r\log n)=O(\log^6n)\).
Step 4: 只需要比较 \(n\) 和 \(r\) 大小.
时间复杂度 \(O(\log n)\).
Step 5: 验证 \(\lfloor\sqrt{\phi(r)}\log n\rfloor\) 个多项式等式.
1. 每个等式次数都是 \(r\), 故单次验证的开销为 \(O^\sim(r\log^2 n)\).
2. 总复杂度为 \(O^\sim(r\sqrt{\phi(r)}\log^3n)\).
综上,Step 5的复杂度为 \(O^\sim(r\sqrt{\phi(r)}\log^3n)=O^\sim(r^\frac{3}{2}\log^3n)=O^\sim(\log^\frac{21}{2}n)\).
Step 6: 这步啥也没干, 就返回了一个PRIME.
时间复杂度 \(O(1)\).
综上, 算法的时间复杂度为 \(O(\log^\frac{21}{2}n)\).
至此, 算法复杂度证明完毕.
- 貌似还有一些改进, 有点麻烦, 以后再说.
一些引理的证明细节
LEMMA 1 Proof. \(\forall 0<i<n\), \(x^i\) 在 \(((x+a)^n-(x^n+a))\) 中的系数为 \(\binom{n}{i}a^{n-i}\).
- 若 \(n\) 为素数, 则 \(\binom{n}{i}=0~({\rm mod~n})\), 故 \(\forall 0<i<n\), \(x^i\) 系数均为 \(0\), 即原式成立.
- 若 \(n\) 为合数, 取 \(q~\vert~n\), 且 \(q^k~||~n\). 则 \(q^k\) 不能整除 \(\binom{n}{q}\), 且 \((q,a^{n-q})=1\). 故 \(x^q\) 系数不为 \(0\). 故原式不成立.
综上, 原式成立当且仅当 \(n\) 是素数.
LEMMA 2 Proof. 考虑积分 \[I(m,n)=\int_0^1 x^{m-1}(1-x)^{n-m}{\rm d}x\quad (1\leqslant m\leqslant n).\] 一方面, 由 \((1-x)^{n-m}\) 的展式可知 \(I(m,n)\) 是分母整除 \({\rm LCM}(n)\) 的有理数: \[I(m,n)=\sum\limits_{0\leqslant j\leqslant n-m}(-1)^j\binom{n-m}{j}\frac{1}{m+j}\in\frac{1}{d_n}\mathbb{Z}.\] 另一方面, 注意到 \(\forall 0\leqslant y\leqslant 1\), 有 \[\sum\limits_{1\leqslant m\leqslant n}\binom{n-1}{m-1}y^{m-1}I(m,n)=\int_0^1(1-x+xy)^{n-1}{\rm d}x=\frac{1}{n}\sum\limits_{1\leqslant m\leqslant n}y^{m-1}.\] 从而 \[I(m,n)=\frac{1}{n}\binom{n-1}{m-1}=\frac{1}{m}\binom{n}{m}\quad (1\leqslant m\leqslant n).\] 这说明对 \(1\leqslant m\leqslant n\), 有 \(m\binom{n}{m}~\vert~d_n\). 于是有 \[\left.\left.n\binom{2n}{n}~\right|~{\rm LCM}(2n)~\right|~{\rm LCM}(2n+1)~~且~~\left.(n+1)\binom{2n+1}{n}=(2n+1)\binom{2n}{n}~\right|~{\rm LCM}(2n+1).\] 由于 \((n,2n+1)=1\), 故 \[\left.n(2n+1)\binom{2n}{n}~\right|~{\rm LCM}(2n+1).\] 由于 \(\binom{2n}{n}\) 是 \((1+x)^{2n}\) 系数中最大的一项, 故 \[{\rm LCM}(2n+1)\geqslant n4^n\quad (n\geqslant 1).\] 从而 \[{\rm LCM}(2n+1)\geqslant 2\cdot 4^n=2^{2n+1}\quad (n\geqslant 2).\] 且 \[{\rm LCM}(2n+2)\geqslant {\rm LCM}(2n+1)\geqslant 4^{n+1}\quad (n\geqslant 4).\] 以上已经证明了对于 \(n\geqslant 9\) 有 \({\rm LCM}(n)\geqslant 2^n\). 经验证 \(n=7,8\) 也成立, 于是原式对 \(\forall n\geqslant 7\) 成立.
LEMMA 4 Proof. 当 \(n=2\) 时, 取 \(r=3\) 即可. 故以下假设 \(n>2\), 即有 \(\lceil\log^5n\rceil>10\) 且 LEMMA 2 适用.
先证存在 \(r\leqslant m\), s.t. \(r\not| N\), 其中 \[N=n^{\lfloor \log m\rfloor}\cdot\prod\limits_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1).\] 假设 \(r~\vert~N\), \(\forall 1\leqslant r\leqslant m\), 则有 \({\rm LCM}(m)\leqslant N\). 注意到 \[ \begin{align} N &= n^{\lfloor \log m\rfloor}\cdot\prod\limits_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1) \\ &< n^{\lfloor \log m\rfloor}\cdot\prod\limits_{i=1}^{\lfloor\log^2n\rfloor}n^i \\ &= n^{\lfloor\log m\rfloor+1+2+\cdots+\log^2n} \\ &= n^{\lfloor\log m\rfloor+\frac{1}{2}[\log^2n(\log^2n+1)]} \\ &= n^{\lfloor\log m\rfloor+\frac{1}{2}[\log^4n+\log^2n]} \\ &< n^{\log^4n} \\ &= (2^{\log n})^{\log^4n} \\ &= 2^{\log^5n} \leqslant 2^m. \end{align} \] 故 \(N<2^m\), 这与 \({\rm LCM}(m)\geqslant 2^m\) 矛盾. 故集合 \(\{r~|~1\leqslant r\leqslant m,~r\not| N\}\) 非空. 设 \(r\) 为其中的最小值.
至此我们已经找到了 \(r\leqslant m\), 以下只需证明 \(o_r(n)\) 存在, 且 \(o_r(n)>\log^2n\). 由于 \(o_r(n)\) 存在当且仅当 \((r,n)=1\), 故只需证明 \(r\) 与 \(n\) 互素. 设 \(r=ab\), 其中 \(a\) 由 \((n,r)\) 的所有素因子组成, \(b\) 由其他素因子组成, 即 \((a,b)=1\). 显然有 \((b,n)=1\).
注意到 \(a\) 的任意素因子在 \(a\) 中的最高幂次都不会超过 \(\lfloor\log m\rfloor\), 否则 \(a\leqslant r\) 会超过 \(m\). 故 \(a\) 的任意素因子在 \(a\) 中的幂次都不超过在 \(n^{\lfloor\log m\rfloor}\) 中的幂次, 故 \(a~|~n^{\lfloor\log m\rfloor}\).
另一方面, 有 \(b\not|n^{\lfloor \log m\rfloor}\cdot\prod\limits_{i=1}^{\lfloor\log^2n\rfloor}(n^i-1)\) 且由 \((b,n)=1\) 可知 \(b\not| n^{\lfloor\log m\rfloor}\). 故 \(b\not| N\). 然而由 \(r\) 的定义可知, \(r\leqslant b\), 于是有 \(r=b\). 故 \((r,n)=1\), 故 \(o_r(n)\) 存在.
最后证明 \(o_r(n)>\log^2n\): 假设 \(d=o_r(n)\leqslant\log^2n\), 则由定义有 \(n^d=1~({\rm mod}~r)\), 即 \(n^d-1=0~({\rm mod}~r)\), 故 \(n~|~(n^d-1)\). 即 \(r\) 整除 \(N\) 的一个因子 \(n^d-1\), 因而 \(r~|~N\), 矛盾! 于是有 \(o_r(n)>\log^2n\).
至此, 引理得证.
LEMMA 7 Proof. 注意到 \(h(x)\) 是 \(r\) 次分圆多项式 \(Q_r(x)\) 的一个因式, \(x\) 为 \(F\) 上的 \(r\) 次本原单位根. 以下证明: \(P\) 中任意两个不同的次数不超过 \(t\) 的多项式在 \(\mathcal{G}\) 中会对应到不同的元素.
设 \(f(x),g(x)\in P\) 是这样的两个多项式. 假设 \(f(x)=g(x)\) 在 \(F\) 上成立. 取 \(m\in I\), 则在 \(F\) 中有 \([f(x)]^m=[g(x)]^m\). 由于 \(m\) 对 \(f\) 和 \(g\) 都是introspective的, 且 \(h(x)~\vert~x^r-1\), 故 \[f(x^m)=g(x^m)\quad\text{in}~F.\] 这说明 \(\forall m\in G\), \(x^m\) 总是多项式 \(Q(y)=f(y)-g(y)\) 的根. 由于 \(m\in G\subset\mathbb{Z}_r^*\), 故 \((m,r)=1\), 故每个这样的 \(x^m\) 都是 \(r\) 次本原单位根. 故这样得到了 \(Q(y)\) 的 \(\vert G\vert=t\) 个不同的根. 然而 \(Q(y)\) 的次数小于 \(t\), 故根也少于 \(t\) 个. 矛盾! 故在 \(F\) 上有 \(f(x)\neq g(x)\).
注意到 \(l=\lfloor\sqrt{\phi(r)}\log n\rfloor<\sqrt{r}\log n<r\) 且 \(p>r\), 故 \(x,x+1,\cdots,x+l\) 在 \(F\) 中两两不等. 同时, 由 \(h(x)\) 的次数大于 \(1\) 可知, \(x+a\neq 0\), \(\forall 0\leqslant a\leqslant l\). 于是 \(\mathcal{G}\) 中存在至少 \(l+1\) 个一次多项式. 故 \(\mathcal{G}\) 中至少存在 \(\binom{t+l}{t-1}\) 个次数小于 \(t\) 的多项式.
LEMMA 8 Proof. 考虑 \(I\) 的以下子集: \[\hat{I}=\{(\frac{n}{p})^i\cdot p^j~\vert~0\leqslant i,j\leqslant\lfloor\sqrt{t}\rfloor\}.\] 若 \(n\) 不是 \(p\) 的方幂, 则 \(\hat{I}\) 有 \((\lfloor\sqrt{t}\rfloor+1)^2>t\) 个不同元素.
由于 \(|G|=t\), 故由抽屉原理可知 \(\hat{I}\) 中至少存在 \(2\) 个元素模 \(r\) 同余. 令其为 \(m_1,m_2\), 不妨设 \(m_1>m_2\). 则有: \[x^{m_1}=x^{m_2}~({\rm mod}~x^r-1).\] 令 \(f(x)\in P\), 则 \[ \begin{align} [f(x)]^{m_1} &= f(x^{m_1})~({\rm mod}~x^r-1,p) \\ &= f(x^{m_2})~({\rm mod}~x^r-1,p) \\ &= [f(x)]^{m_2}~({\rm mod}~x^r-1,p). \end{align} \] 即在 \(F\) 上有 \([f(x)]^{m_1}=[f(x)]^{m_2}\). 于是 \(f(x)\in\mathcal{G}\) 是多项式 \(Q'(y)=y^{m_1}-y^{m_2}\) 在 \(F\) 中的一个根. 由于 \(f(x)\) 是 \(\mathcal{G}\) 中的任意一个元素, 故 \(Q'(y)\) 在 \(F\) 中至少有 \(|\mathcal{G}|\) 个不同的根. 而 \[{\rm deg}~Q'(y)=m_1\leqslant (\frac{n}{p}\cdot p)^{\lfloor\sqrt{t}\rfloor}.\] 即 \(|\mathcal{G}|\leqslant n^{\lfloor\sqrt{t}\rfloor}.\)