论文翻译：《PRIMES is in P》——素性测试的确定性多项式时间算法研究

由引理3.1，前\(\lceil\log^5n\rceil\)个数的公倍数至少为\(2^{\lceil\log^5n\rceil}\),而\(r_1,r_2,\cdots,r_t\)的最小公倍数小于\(n\cdot\prod_{i=1}^{\lfloor \log^2n\rfloor}(n^i-1)\)，故\(\exists s\le \lceil\log^5n\rceil\)使得\(s\notin \{r_1,r_2,\cdots,r_t\}.\)

若\((s,n)=1\)，则\(o_s(n)>\log^2n\)，\(s\)即为所求

若\((s,n)\ne 1\)，因为\(s\)不整除\(n\)，且\((s,n)\in \{r_1,r_2,\cdots,r_t\}\).\(r=\frac s{(s,n)}\notin \{r_1,r_2,\cdots,r_t\}\)，所以\(o_r(n)>\log ^2n\).

由于\(o_r(n)>1\)，则必存在\(n\)的一个素因子\(p\)，使得\(o_r(p)>1\).我们有\(p>r\)，否则在第3，第4步就可以判定\(n\)是否是素数。因为\((r,n)=1\)（如若不然，在第三步或第四步就可以判定\(n\)是否是素数），因此\(p,n\in Z_r^*\)。

令\(l=\lfloor\sqrt{\phi(r)}\log n\rfloor\).算法第五步，验证\(l\)个方程。因为算法在此步不输出COMPOSITE，所以有：

对于任意的\(a,0\le a\le l\)（平凡地，\(a=0\)显然成立），可知：

对于\(\forall a, 0\le a\le l\)，由引理2.1，我们有：

对于\(\forall a, 0\le a\le l\)，由方程(3)和(4)，我们有：

对于\(\forall a, 0\le a\le l\)，在上面的方程中，\(n\)和\(n/p\)的性质类似于素数\(p\)，我们对于以上的等式性质给出一个定义：

定义4.4：对于多项式\(f(X)\)和整数\(m\in {\mathbb N}\)，如果：

\[[f(X)]^m\equiv f(X^m)({\rm mod \ }X^r-1,p) \]

则我们称\(m\)是\(f(X)\)的自省数。

由方程(5)和(4)，我们可以看出，当\(0\le a\le l\)时，\(p\)和\(n/p\)都是\(X+a\)的自省数。

接下来的引理证明了自省数在乘法下封闭。

引理4.5：如果\(m\)和\(m‘\)是\(f(X)\)的自省数，则\(m\cdot m‘\)也是\(f(X)\)的自省数。

证明：由于\(m\)是\(f(X)\)的自省数，我们有：

由于\(m‘\)也是\(f(X)\)的自省数，我们有：

又因为\(X^r-1\)整除\(X^{m\cdot r}-1\)，则上式

证毕。

引理4.6：对于数\(m\)，以\(m\)为自省数的多项式集合对乘法封闭。即：如果\(m\)是\(f(X)\)和\(g(X)\)的自省数，那么\(m\)也是\(f(X)\cdot g(X)\)的自省数。

证明：

以上两个引理说明：对于集合\(I=\{(n/p)^i\cdot p^j|i,j\ge 0 \}\)中的任意一个数，它都是集合\(P=\{\prod_{a=0}^l(X+a)^{e_a}|e_a\ge 0 \}\)中任意一个多项式的自省数。在此基础上我们定义两个群，它们将在后面的证明中起到重要的作用。

第一个群是集合\(I\)中的数模\(r\)的余数构成的群，即：

由于\((n,r)=(p,r)=1\)，所以它是\(Z_r^*\)的子群。设\(|G|=t\),\(G\)由\(n\)和\(p\)模\(r\)生成，因为\(o_r(n)>\log ^2n\)，所以\(t>log^2n\).

要定义第二个群，我们需要一些关于有限域上分圆多项式的基础事实。令\(Q_r(X)\)为域\(F_p\)上的\(r\)次分圆多项式。多项式\(Q_r(X)\)整除\(X^r-1\)，并且\(Q_r(X)\)可以分解为次数为\(o_r(p)\)的不可约多项式。令\(h(X)\)是一个不可约因式，因为\(o_r(p>1)\)，所以\(h(X)\)的次数大于1。第二个群是\(P\)中多项式模\(h(X)\)和\(p\)的余式构成的集合。设这个群为 \({\mathcal G}=\langle X({\rm mod\ }h(X,p)) ,X+1({\rm mod\ }h(X,p)),\cdots,X+l({\rm mod\ }h(X,p))\rangle\).令\(F=F_p[X]/(h(X))\) ，则\(\mathcal G\)是乘法群\(F\)的一个子群。

以下引理给出了群\(\mathcal G\)的阶的一个下界，它由Hendrik Lenstra Jr.证明，并对我们早期研究中给出的算法的下界作了些许改进。

引理4.7（Hendrik Lenstra Jr.引理）

\[|{\mathcal G}|\ge\left(\begin{array}{c}t+l\\t-1\end{array}\right) \]

作者注：Macaj也曾独立地证明了这个引理。

证明：首先我们注意到\(h(X)\)是分圆多项式\(Q_r(X)\)的因子，所以在\(F\)中\(X\)是它的一个\(r\)次本原单位根。接下来我们证明，任意两个次数小于\(t\)的多项式可以映射到\(\mathcal G\)中的不同元素。设\(f(X)\)和\(g(X)\)是\(P\)中的两个多项式，且\(\deg f(X).设在\(F\)中\(f(X)=g(X)\)，即\(f(X)\equiv g(X)({\rm mod}\ h(X),p)\).再设\(m\in I\)，则

由于\(m\)是\(f(X),g(X)\)的自省数，且\(h(X)\)整除\(X^r-1\)，我们得到：

这意味着对于\(\forall m\in G\)，\(X^m\)是多项式\(Q(Y)=f(Y)-g(Y)\)的根。由于\((m,r)=1\)，\(G\)是\(Z_r^*\)的子群，任意一个如上的\(X^m\)都是\(r\)次本原单位根，因此多项式\(Q(Y)\)在\(F\)中一共有\(|G|=t\)个不同的根。但是因为\(f\)和\(g\)的次数都小于\(t\)，\(Q(Y)\)的次数小于\(t\)，从而推出矛盾。因此，\(f(X)\not\equiv g(X)({\rm mod}\ h(X),p)\).

注意到对于\(F_p\)中的\(1\le i\ne j\le l\)，\(i\ne j\).且\(l=\lfloor \sqrt{\phi(r)}\log n\rfloor .所以在\(F\)中\(X,X+1,X+2,\cdots,X+l\)两两不等。同时，因为\(h\)次数大于1，\(X+a\ne 0\)对于\(F\)中的任意一个\(a,0\le a\le l\)都成立，所以\(\mathcal G\)中至少有\(l+1\)个不同的一次多项式。因此\(\mathcal G\)中至少存在\(\left(\begin{array}{c}t+l\\t-1\end{array}\right)\)个次数小于\(t\)的不同的多项式。证毕。

若\(n\)不是素数\(p\)的方幂，那么我们可以给出\(\mathcal G\)的阶的一个上界。

引理4.8：如果\(n\)不是素数\(p\)的方幂，那么\(|{\mathcal G}|\le n^{\sqrt t}\)。

证明：考虑以下\(I\)的子集

如果\(n\)不是\(p\)的方幂，那么集合\(\hat I\)中有\((\lfloor \sqrt t\rfloor )^2>t\)个不同的数。又因为\(|G|=t\)，\(\hat I\)中至少存在两个数在模\(r\)意义下相等。不妨设这两个数分别是\(m_1,m_2\)，且\(m_1>m_2\).于是我们有：

设\(f(X)\in P\).那么：

这意味着在域\(F\)中

因此，\(f(X)\in {\mathcal G}\)是域\(F\)中的多项式\(Q‘(Y)=Y^{m_1}-Y^{m_2}\)的根。由于\(f(X)\)具有任意性，多项式\(Q‘(Y)\)在域\(F\)中至少具有\(|\mathcal G|\)个互不相等的根。又

也就证明了\(|{\mathcal G}|\le n^{\sqrt t}\)，证毕。

有了以上的准备，我们现在可以证明算法的正确性了。

引理4.9：如果算法返回PRIME，那么\(n\)是素数。（必要性）

证明：假设算法返回PRIME，由引理4.7，对于\(t=|G|\)和\(l=\lfloor \sqrt{\phi (r)}\log n\rfloor\)，有

由引理4.8，若\(n\)不是素数\(p\)的方幂，则${|\mathcal G|}\le n^{\sqrt t} $.因此由上述不等式，可知：

若\(k>1\)，则算法在第一步返回COMPOSITE，因此这里的情况只能是\(n=p\)。这就完成了对定理4.1的证明。

第五部分：分析算法时间复杂度的界限

我们计算复杂度基于以下事实：两个长为\(m\)比特的数的加法，乘法，出发运算时间复杂度是\(O^{\sim}(m)\).类似的，两个次数为\(d\)、系数至多为\(m\)比特的多项式的运算的时间复杂度是\(O^{\sim}(d\cdot m)\).

定理5.1：算法的渐进时间复杂度是\(O^{\sim }(\log ^{21/2}n)\).

证明：算法的第一步渐进时间复杂度为\(O^{\sim }(\log ^{3}n)\).

在算法的第二步，我们要找一个满足\(o_r(n)>\log ^2 n\)的\(r\)，这可以通过验证对于每一个\(r,\forall k,1\le k\le \log ^2 n\)，是否满足$n^k\not\equiv1({\rm mod}\ r) \(.对于一个固定的\)r\(，计算\)n^k({\rm mod\ }r)\(需要作至多\)O(\log ^2 n)\(次模\)r\(乘法，所需时间复杂度为\)O(\log ^2n\log r)\(.由引理4.3我们知道只需检验\)O(\log ^5 n)\(个不同的\)r\(的值。因此第二步的时间复杂度为\)O^{\sim }(\log ^7n)$.

算法第三步包括计算\(r\)对数的最大公因数。求最大公因数的时间复杂度是\(O(\log n)\)，因此这一部的时间复杂度是\(O(r\log n)=O(\log ^6n).\)

算法第四步复杂度仅为\(O(\log n)\).

算法第五步，我们需要验证\(\lfloor \sqrt{\phi(r)}\log n\rfloor\)个方程。验证每个方程需要\(O(\log n)\)次次数为\(r\)，系数大小为\(O(\log n)\)的多项式乘法。所以验证每个方程需要的时间开销为\(O^{\sim }(r\log ^2n)\)。因此第五步的总时间复杂度为

这个时间复杂度已经涵盖了其它步骤的复杂度，因此算法整体的时间复杂度为\(O^{\sim}(\log^{21/2}n).\)证毕。

通过改进对整数\(r\)的估计精度（由引理4.3），算法的时间复杂度还可以进一步优化。对于最好的情况，即\(r=O(\log^2n)\)时，总的时间复杂度为\(O^{\sim}(\log ^6n)\).事实上，有两个猜想可以支持\(r=O(\log^2n)\)的可能性。（以下的\(\ln\)以自然对数的底数\(e\)为底）

Artin猜想：

对于给定的\(n\in {\mathbb N}\)，且\(n\)不是完全平方数，则满足\(o_q(n)=q-1\)且\(q\le m\)的素数\(q\)的个数渐进为\(A(n)\cdot \frac m{\ln m}\).这里的\(A(n)\)称为Artin常数，\(A(n)>0.35\).

苏菲·姬曼（Sophie Germain）素数密度猜想：

满足\(2q+1\)仍为素数的素数\(q\le m\)的个数渐进为\(\frac {2C_2m}{\ln ^2m}\).这里的\(C_2\)是孪生素数常数，其值约为0.66。具有上述性质的素数\(q\)称为Sophie Germain素数。

令\(m=O(\log ^2n)\)，若Artin猜想成立，立刻可得存在满足要求的\(r=O(\log^2n)\)。在引用文献[GM],[GMM],[HB]中，它们已经对Artin猜想的证明做了一些工作，而且，在广义黎曼猜想的基础上，Artin猜想是成立的。

若Sophie Germain猜想成立，我们可得\(r=O^{\sim}(\log ^2n)\):

由Sophie Germain素数密度猜想，对于一个合适的常数\(c\)，在\(8\log ^n\)和\(c\log^2n(\log \log n)^2\)之间一定存在至少\(\log ^2n\)个Sophie Germain素数。对任意一个这样的素数\(q\)，必定满足以下两条性质其一：

①：\(o_q(n)\le 2\)

②：\(o_q(n)\ge (q-1)/2\)

满足①的任意素数\(q\)必整除\(n^2-1\)，由此可知这样的\(q\)的个数的上界为\(O(\log n)\).这指出了一定存在一个素数\(r=O^{\sim }(\log ^n)\)使得\(o_r(n)>\log ^2 n\).这样的\(r\)就使得我们的算法复杂度变为\(O^{\sim}(\log ^6n)\).

对Sophie Germain素数密度猜想的证明也已有所进展。记\(P(m)\)为\(m\)的最大素因子，Goldfeld[Gol]已经证明了满足\(P(q-1)>q^{\frac 12+c},c\approx \frac 1{12}\)的素数\(q\)以正密度出现。基于以上基础，Fouvry证明了以下结果

引理5.2：

\[\exists c>0,n_0\\ {\rm s.t.\quad } \forall x\ge n_0:\\|\{q|q是素数且q\le x\ 且 \ P(q-1)>q^{\frac23} \}|\ge c\frac x{\ln x} \]

以上引理中的指数精度还可以提高到\(0.6683\).使用以上引理我们可以优化算法的时间复杂度。

定理5.3：算法的时间复杂度是\(O^{\sim}(\log ^{15/2}n)\).

如以上叙述所说，由于满足\(P(q-1)>q^{2/3}\)的素数\(q\)密度较高，以至于在算法的第二部能够找到满足\(o_r(n)>\log ^2n\)的\(r=O(\log ^3n)\).这就将我们的算法复杂度降低到了\(O^{\sim}(\log^{15/2}n)\).证毕。

最近，Hendrik Lenstra和Carl Pomerance对我们的算法做出了改进，可以证明修改版的算法复杂度为\(O^{\sim}(\log^6n)\).

第六部分：将来的工作

我们的算法第五步循环需要进行$\lfloor \sqrt{\phi(r)}\log n\rfloor \(次，以保证群\)\mathcal G\(的阶足够大。如果我们可以证明由较少的\)(X+a)$也能生成同样结束的群，则循环的迭代次数可以减少。这是极有可能的。

若以下猜想成立，算法的复杂度还可以进一步优化至\(O^{\sim}(\log ^3n)\)（引用文献[BP]提出了此猜想，并在[KS]中验证了\(r\le 100,n\le 10^{10}\)的情况）。

猜想6.1：对素数\(r\)，如果\(r\)不整除\(n\)且满足

\[(X-1)^n\equiv X^-1({\rm mod\ }X^r-1,n).\tag6 \]

则\(n\)要么是一个素数，要么\(n^2\equiv 1({\rm mod \ }r)\).

如果以上猜想成立，我们可以略微修改一下算法，首先寻找不整除\(n^2-1\)的整数\(r\)，这样的\(r\)必可在\([2,4\log n]\)区间内找到。这是因为小于\(x\)的素数的乘积不小于\(e^x\)（见引用文献[Apo]）.然后我们需要验证同余式(6)是否成立，其时间复杂度为\(O^{\sim}(r\log^2n)\).这使得算法的整体时间复杂度降低到了\(O^{\sim}(\log ^3 n)\).

最近，Hendrik Lenstra和Carl Pomerance[LP2]认为上述猜想是错误的，但尽管如此，这个猜想的一些变体仍然可能是正确的。（例如强行令\(r>\log n\)的情况）.

致谢

我们感谢Hendrik Lenstra Jr.允许我们使用他的一些发现来改进群\(\mathcal G\)的阶的下界，这使得算法的证明过程变得简单（在早期版本的证明中需要用到引理5.2给出的密度界限），并且改善了时间复杂度！

我们也非常感谢Adam Kalai, Amit Sahai和Madhu Sudan允许我们在引理4.8中引用了他们的证明。这使得对群\(\mathcal G\)的阶的上界和下界的证明方法类似。（它们都通过一个域上多项式的根的数量来进行证明）

感谢Somenath Biswas, Rajat Bhattacharjee, Jaikumar Radhakrishnan和V.Vinay的许多有用的讨论。

感谢Erich Bach, Abhijit Das, G.Garman, Roger Heath-Brown, Pieter Moree, Richard Pinch和Carl Pomerance为我们提供了有用的参考文献。

自从我们的预印版本发布以来，许多研究人员指出了我们论文中存在的各种各样的疏忽之处，我们感谢所有这些研究人员。我们尽量在论文中采纳了他们的建议，对于那些没有采用的建议，我们表示歉意。

最终，我们感谢那些提出了有用的建议和相关研究的匿名引用作者。

参考文献

（译者注：这部分参考文献请看原文pdf第13页到第14页）

论文翻译：《PRIMES is in P》——素性测试的确定性多项式时间算法研究

标签：结束   版本   nat   而且   gmm   映射   inline   最坏情况   曲线   

原文地址：https://www.cnblogs.com/allegro-vivace/p/12892568.html