2  素数判定

素数判定(Primality Test)是一个数论中十分基本,却又趣味盎然的问题.判定一个整数是否是素数,最为朴素的想法是直接利用素数的定义,用小的素数去一一试除,如果能整除的话,那就能确定无疑为合数了.根据Mertens定理（参见(M. Mendès France and Tenenbaum著，姚家燕译 2007)），可以估算出大约有76%的奇数有小于100的素因子,可见这种最平凡的方法有时十分有效.在本章中，我们将用\(N\)来表示待判定的目标数.

相比整数的因子分解，素数判定一直以来被认为是较为容易的问题。2002年三位印度计算机科学家Agrawal，Kayal，Saxena(Agrawal, Kayal, and Saxena 2004)找到了素数判定的多项式算法（被称为AKS算法），其时间复杂度为\(O(\ln^{12} N)\)。AKS算法在理论上有重要的意义，不过实践中还要更多地考虑效率问题。实践中的素数检测方法大致分为两类，一类是确定性的，例如Lehmer \(N-1\)检测，Lucas \(N+1\)检测，椭圆曲线素性证明(ECPP)等等，当输出结果为”素数”时，能够保证被检测数一定为素数；另一类是概率性的，如Rabin-Miller检测，Baillie-PSW检测等等，当输出结果为”素数”时，仅以一定的高概率保证被检测数的素性。不过概率性检测一般要比确定性检测快得多。

APRCL方法将Fermat类型的想法运用到分圆域中,最先由Adleman,Pomerance,Rumely(Adleman 1980)提出,后经Cohen,Lenstra(H. Cohen and Lenstra 1984)的改进，时间复杂度为”近似”多项式的\(O((\ln N)^{c\ln\ln\ln N})\)，其中\(c\)为一个常数。椭圆曲线素数证明最早由Goldwasser,Kilian(Goldwasser and Kilian 1986)提出，后经Atikin，Morain(Atkin and Morain 1993)改进和实现，平均时间复杂度达到了\(O(\ln^6 N)\)。这两种方法已经成为目前实践上最快的确定性检测方法，并在密码学等领域有重要的应用。鉴于我们的目的，不能用太多篇幅来介绍这两种方法，详细可参阅文献(Henri Cohen 1993).

有些素数判定方法严格来说应当是合性检测(Compositeness Test),这类方法总可以有效地把素数判定出来,而有可能把一个合数判定为素数.也就是说,此类方法判定一个数为合数总是准确无误的,而”漏网的”,即无法判定的合数往往称为伪素数(Pseudoprimes).

阅读本章需要读者初等数论和抽象代数的基础知识（例如(冯克勤 2003),(聂灵沼，丁石孙 2000)）。本章的主要参考书是(Riesel 1985)，(Henri Cohen 1993)和(裴定一，祝跃飞 2002).读者也可以参考写的十分通俗易懂的(颜松远 2008)及其他算法/计算数论方面的相关文献。

2.1 Fermat检测

几乎所有素数检测的想法之基石均为著名的Fermat小定理，即若\(p\)为素数，\((a,p)=1\)，则

\[ a^{p-1}\equiv1\pmod{p}. \]

由此我们得到最简单的检测算法——Fermat合性检测。

Definition 2.1 (算法：Fermat 小定理作为合性检测) 任取整数\(a\)，如果\((a,N)=1\)且\(a^{N-1}\not\equiv1\pmod{N}\)，则输出\(N\)为合数，否则输出\(N\)可能为素数。

Definition 2.2 (Fermat 伪素数) 满足 \(a^{N-1}\equiv1\pmod{N}\) 的合数 \(N\) 称为一个(对于基\(a\))的 Fermat伪素数。

在\(25\times10^9\)以下，有21853个对于基\(a=2\)的Fermat伪素数（参考(Pomerance, Selfridge, and Wagstaff 1980)），如果对其再进行基为\(a=3\)的检测的话，伪素数将还剩下4709个，对于\(a=2,3,5\)有2552个，\(a=2,3,5,7\)有1770个。

运用Fermat检测的关键是如何快速计算\(a^{d} \mod N\)。求幂运算采取二进算法 Definition 4.1 ，Definition 4.2 ，可以使Fermat检测的算法复杂度降到平均\(1.5\log N\cdot M(N)\)（其中\(M(N)\)表示乘法运算的复杂度），已经为多项式阶的算法了。使用Montgomery约化算法@def-al:monredc 可以更进一步地提高速度。

Camichael数是看起来比Fermat伪素数条件更”苛刻”的一类数。

Definition 2.3 (Camichael 数) 如果合数\(N\)，对任意满足\((a,N)=1\)的整数\(a\)都有\(a^{N-1}\equiv1\pmod{N}\)，则称\(N\)为Camichael数。

也就是说，Camichael数都将会是Fermat检测的”漏网之鱼”。最小的Camichael数的例子是\(561=3\cdot 11\cdot 17\)。在\(25\times10^9\)以下一共有2163个Camichael数，它比对基\(a=2,3,5,7\)的Fermat伪素数还要来得多的原因是，如果恰巧\(N\)有2,3,5,7的因子，\(N\)便可以是Camichael数而非Fermat伪素数。

2.2 Euler 检测

Euler检测基于Euler的二次剩余定理，即若\(p\)为奇素数，\((a,p)=1\)，则\[ a^{(p-1)/2}\equiv\legendre{a}{p}\pmod{p}. \]

其中\(\legendre{a}{p}\)是Legendre符号。

Definition 2.4 (算法：Euler判则作为合性检测) 设\(N\)为奇数，任取整数\(a\)，满足\((a,N)=1\)：

  1. 如果 \(a^{(N-1)/2}\not\equiv\pm1\pmod{N}\)，则输出\(N\)为合数。
  2. 如果 \(a^{(N-1)/2}\equiv\pm1\pmod{N}\) 且 \(a^{(N-1)/2}\not\equiv\legendre{a}{N}\pmod{N}\)，则输出\(N\)为合数。
  3. 如果 \(a^{(N-1)/2}\equiv\legendre{a}{N}\pmod{N}\)，则输出\(N\)可能为素数。

Definition 2.5 (Euler伪素数) 如果合数\(N\)，\((a,N)=1\)，满足\(a^{(N-1)/2}\equiv\legendre{a}{N}\pmod{N}\)，则称\(N\)为(对于基\(a\)的)Euler伪素数。

Definition 2.6 (强伪素数) 设\(N\)奇合数，\(N-1=d\cdot 2^s\)，\(d\)为奇数。\(N\)被称为(对于基\(a\)的)强伪素数，如果\[ a^d\equiv 1 \pmod{N} \]或者对于某一个\(r(0\le r\le s-1)\)有\[ a^{d\cdot 2^r}\equiv -1 \pmod{N}. \]

Remark 2.1. 强伪素数的定义可以这样看出：若\(N\)为素数，则\[\begin{align*} a^{N-1}-1&=(a^d-1)(a^d+1)(a^{2d}+1)(a^{4d}+1)\cdots(a^{2^{s-1}d}+1)\\ &\equiv 0\pmod{N}. \end{align*}\]

对于Euler伪素数和强伪素数均不会出现类似Fermat伪素数的情况，也就是说，只要测试的基\(a\)足够多，最终总可以将合数和素数分辩开来。\(25\times10^9\)以下只有13个同时为对基2,3,5的强伪素数。

Remark. (Pomerance, Selfridge, and Wagstaff 1980)证明了，Euler伪素数必定是强伪素数。

2.3 Lehmer \(N-1\) 型检测

Lehmer $N-1$型检测有时候\(N\)的素性很难判定，而\(N\pm1\)的分解却很容易得到。这一节的方法便是依赖于\(N-1\)的素因子分解。

Lehmer 的逆定理

Theorem 2.1 (Fermat小定理逆定理, Lehmer) 设有素因子分解 \(N-1=q_1^{\beta_1}\cdots q_n^{\beta_n}\)。如果对 \(a\) 有\[ a^{(N-1)/q_j}\not\equiv1 \pmod{N},\qquad \forall j=1,2,\ldots,n, \]且\[ a^{N-1}\equiv1 \pmod{N} . \tag{2.1}\]

则\(N\)为素数。

Proof. 从简化剩余系的乘法群 \(M_N=(\mathbb{Z}/N\mathbb{Z})^*\) 角度来看，条件保证了\(a\)为\(M_N\)的一个\(N-1\)阶元素，而 \(|M_N|=\varphi(N)\) (\(\varphi\) 为Euler函数)，从而有\(\varphi(N)\ge N-1\)，这就保证了\(N\)为素数。

Remark. 这里不要\((a,N)=1\)的条件，是因为其已经被包括在式 Equation 2.1 之中了。

寻找\(M_N\)的生成元(甚至只寻找模\(N\)的一个二次剩余)都是非常困难的事情，目前还没有有效的确定性的方法。一个现实的问题是如果\(N\)为伪素数，如何才能快速的找到Lehmer \(N-1\)检测中符合条件的\(a\)，即\(M_N\)的一个生成元呢？有一些步骤可以采用：

  1. 排除所有\(\legendre{a}{N}=1\)的\(a\)，这就排除了一半可能的\(a\)！
  2. 从较小的\(q_j\)开始检测，因为\(q_j\)越小，失败的可能性越大。

Selfridge的多基推广

Theorem 2.2 (Selfridge的多基推广) 如果\(\forall q_j\)，\(\exists a_j\)使得\[ a_j^{(N-1)/{q_j}}\not\equiv1 \pmod{N} \]且\[ a_j^{N-1}\equiv1 \pmod{N} . \]则\(N\)为素数。

Proof. 设\(a_j\)模\(N\)的阶为\(r_j\)，则以上两式表明 \(r_j\nmid\frac{N-1}{q_j}\) 且 \(r_j\mid N-1\)，从而\(q_j^{\beta_j}\mid r_j\Rightarrow N-1\mid \varphi(N) \Rightarrow \varphi(N)=N-1\)。

Remark. 这个方法对\(M_N\)的生成元很大的时候非常有用，因为我们不必找出一个”共同”的\(a\)来。

Pepin定理

Theorem 2.3 (Pepin定理) 设\(F_n=2^{2^{n}}+1\)为Fermat素数(\(n\ge1\))。则\(F_n\)为素数当且仅当\[ 3^{2^{2^{n-1}}}\equiv-1 \pmod{F_n} \]

Proof. 用定理 Theorem 2.1 即可，只需注意到3必为\(12n\pm 5\)型素数的二次非剩余。

Remark. 使用这个方法，在1963年(Selfridge and Hurwitz 1964)证明了\(F_{14}\)(有4933个十进制位)是合数，尽管但现在为止还不知道其任何一个因子。

下面的定理让我们可以拥有不必完全分解\(N-1\)的便利。

放宽版本

Theorem 2.4 (Lehmer定理的放宽版本) 设\(N-1=RF\)，\((R,F)=1\)且\(R<F\)，有素因子分解\(F=\prod\limits_{j=1}^n q_j^{\beta_j}\)。若有\(a\)使得\[ a^{(N-1)/q_j}\not\equiv1 \pmod{N},\qquad \forall j=1,2,\ldots,n \]且\[ a^{N-1}\equiv1 \pmod{N}, \]则\(N\)为素数。

Proof. 设\(p\)为素数，\(p\mid N\)，设\(a\)模\(p\)的阶是\(d\)，则由条件有\(d\mid N-1\)，但 \(d\nmid \frac{N-1}{q_j}\)。从而\(\forall j\)，\(d\mid \prod\limits_{i=1}^n q_i\)，但\(d\nmid R\cdot q_j^{\beta_j-1}\prod\limits_{i\ne j}q_i^{\beta_i}\)。故有\[ q_j^{\beta_j}\mid d\Rightarrow F\mid d\Rightarrow F\mid p-1 \Rightarrow F\le \sqrt{N}. \]矛盾！

Proth定理

Theorem 2.5 (Proth定理) 设\(N=h\cdot2^n+1\)，其中\(h\)为奇数，\(2^n>h\)。如果存在\(a\)使得\[ a^{(N-1)/2}\equiv-1 \pmod{N} . \]则\(N\)为素数。

Proof. 在定理@thm-RelaxedFermatConverse 中令\(F=2^n\)即得。

2.4 Lucas 伪素数检测与 \(N+1\) 型检测

如果\(N-1\)也是很难分解的，这里的方法就将分解的困难转移到\(N+1\)上去。想法是与\(N-1\)型检测是类似的，不过要将Fermat小定理从 \(\mathbb{Z}\) 上推广到二次域的代数整数环上去，替代那里的\(a^{N-1}-1\)的则是所谓Lucas序列\(U_{N+1}\)。

设\(D\)为无平方整数，记\(O\)为二次域\(\mathbb{Q}(\sqrt{D})\)的代数整数环，我们熟知(参见(聂灵沼，丁石孙 2000)，P139)当\(D\equiv2,3\pmod{4}\)时，\[ O=\{m+n\sqrt{D}\mid m,n\in\mathbb{Z}\}, \]

而当\(D\equiv1\pmod{4}\)时，\[ O=\Big\{\frac{m+n\sqrt{D}}{2}\,\Big\vert\, m,n\in\mathbb{Z},m\equiv n\pmod{2}\Big\}. \]

在\(O\)中可以很容易地讨论同余的概念，称\(a\equiv b\pmod{M}\)，若\(a-b\)属于\(M\)在\(O\)中生成的理想。记\(\bar a\)为\(a\)在\(O\)中的共轭，即\(\overline{r+s\sqrt{D}}=r-s\sqrt{D}\)，则在\(O\)中我们有如下Fermat小定理的类比。

二次域中的

Theorem 2.6 (二次域中的Fermat小定理) 设\(a\in O\)，\(p\)为奇素数，\(p\nmid D\)，则有\[\begin{equation*} a^p\equiv \begin{cases} a&\text{若}\displaystyle\legendre{D}{p}=1\\\noalign{\smallskip} \bar{a}&\text{若}\displaystyle\legendre{D}{p}=-1 \end{cases} \pmod{p}. \end{equation*}\]

Proof. 设\(2a=r+s\sqrt{D}\)，\(r,s\in\mathbb{Z}\)，则由\(\mathbb{Z}\)上的Fermat小定理，二项展开及Euler二次剩余定理得\[\begin{align*} 2a^p&\equiv(2a)^p\equiv(r+s\sqrt{D})^p\equiv r^p+(s\sqrt{D})^p \\ &\equiv r+sD^{\frac{p-1}{2}}\sqrt{D} \\ &\equiv r+s\legendre{D}{p}\sqrt{D}\pmod{p}. \end{align*}\]从而得到所要结论。

定理 Theorem 2.6 中的乘幂不容易计算，为了有效地利用定理 Theorem 2.6 的结论，我们引入Lucas序列的概念，Lucas序列实际上是一类简单的二阶递推序列。

Definition 2.7 (Lucas序列) 设 \(P,Q\in\mathbb{Z}\)，特征方程 \(\lambda^2-P\lambda+Q=0\) 的两根为 \(a\)，\(b\)。则 \(P\)，\(Q\) 对应的 Lucas 序列定义为\[ U_n=\frac{a^n-b^n}{a-b},\qquad V_n=a^n+b^n. \]

Remark. 由特征方程对应的递推关系，知道\(\{U_n\},\{V_n\}\)均为\(\mathbb{Z}\)中的序列。

Lemma 2.1 记号同定义 Definition 2.7 ，设整数\(M\)满足\((QD,M)=1\)，则\(a,b,a-b\)均模\(M\)可逆。并且\(U_k\equiv0\pmod{M}\)当且仅当\((ab^{-1})^k\equiv1\pmod{M}\)。

Proof. 由 \((Q,M)=1\) 知 \(Q\) 模 \(M\) 可逆，而 \(ab=Q\)，知 \(ab\cdot Q^{-1}\equiv1\pmod{M}\)，从而 \(a,b\) 均模 \(M\) 可逆。又 \(a-b=\sqrt{D}\)，而 \(D^{\varphi(M)}\equiv1\pmod{M}\)，可知 \((a-b)^{2\varphi(N)}\equiv1\pmod{M}\)，从而 \(a-b\) 也模 \(M\) 可逆。

由于 \(a-b\) 模 \(M\) 可逆，\(U_k\equiv(a-b)^{-1}(a^k-b^k)\pmod{M}\)，从而 \[U_k\equiv0\pmod{M}\Longleftrightarrow a^k\equiv b^k\pmod{M}\Longleftrightarrow (ab^{-1})^k\equiv1\pmod{M}.\]引理得证。

Theorem 2.7 设 \(p\) 为素数，满足 \((2QD,p)=1\)，记 \(\varepsilon=\legendre{D}{p}\)，则有 \(U_{p-\varepsilon}\equiv0\pmod{p}\)。

Proof. 若 \(\legendre{D}{p}=1\)，则由定理 Theorem 2.6 可知 \(a^{p-1}\equiv b^{p-1}\equiv1\pmod{p}\)，从而 \((ab^{-1})^{p-1}\equiv1\pmod{p}\)，由引理 Lemma 2.1 知 \(U_{p-1}\equiv0\pmod{p}\)。

若 \(\legendre{D}{p}=-1\)，则由定理 Theorem 2.6 可知 \(a^{p+1}\equiv a\bar a\equiv ab\pmod{p}\)，同理 \(b^{p+1}\equiv ba\pmod{p}\)，从而 \((ab^{-1})^{p+1}\equiv1\pmod{p}\)，由引理 Lemma 2.1 知 \(U_{p+1}\equiv0\pmod{p}\)，这就完成了证明。

由上面的定理我们自然地得到 Lucas伪素数 的概念。

Definition 2.8 (Lucas 伪素数) 设 \(N\) 为奇合数，若存在 Lucas 序列 \(\{U_n\}\)使得 \(\varepsilon=\legendre{D}{N}\ne0\)且 \(U_{N-\varepsilon}\equiv0\pmod{N}\)，则称 \(N\) 为 Lucas 伪素数。

正如我们在 Fermat 检测和 Euler 检测中看到的，一个伪素数概念对应着一个合性检测算法，由此我们立即可以得到 Lucas伪素数检测 算法。

Definition 2.9 (算法：Lucas伪素数检测) 选取 Lucas 序列参数 \(P,Q\)，使得 \(\varepsilon=\legendre{D}{N}\ne0\)。若 \(U_{N-\varepsilon}\not\equiv0\pmod{N}\) 则输出 \(N\) 为合数，否则输出 \(N\) 可能为素数。

Remark. 由于来源的不同，我们可以期望一个数同时为 Lucas 伪素数和 Fermat 伪素数（或强伪素数）的可能情形不大，这样的观察也被用于 Baillie-PSW 检测算法 Definition 2.12 中。

我们已经得到了 Lucas 伪素数合性检测，和 \(N-1\) 型检测类似，我们还能够进行素性的确证。在这里，替代 \(N-1\) 的分解的是 \(N+1\) 的分解，我们可以看到下面的定理与定理 Theorem 2.1 是多么的”形似”。

Theorem 2.8 (Lucas 检测) 设有素因子分解 \(N+1=\prod\limits_{j=1}^nq_j^{\beta_j}\)，若有 Lucas 序列 \(\{U_n\}\)，使 \((2QD,N)=1\)，满足 \[(U_{(N+1)/q_j},N)=1,\qquad \forall j=1,2,\ldots,n\]且 \[U_{N+1}\equiv0\pmod{N},\] 则 \(N\) 为素数。

Proof. 设 \(p\) 为 \(N\) 的一个素因子，设 \(k\) 为最小的正整数使得 \((ab^{-1})^k\equiv1\pmod{p}\)。由条件知 \(U_{N+1}\equiv0\pmod{p}\)，\(U_{(N+1)/q_j}\not\equiv0\pmod{p}\)，从而根据引理 Lemma 2.1 知 \(k\mid N+1\)，\(k\nmid (N+1)/q_j,\ \forall j\)，从而 \(k=N+1\)。但根据 \(k\) 的最小性，由定理 Theorem 2.7 必有 \(k\mid q+1\) 或 \(k\mid q-1\)。从而 \(q=N\)，\(N\) 为素数。

与 \(N-1\) 型检测完全类似还可以得到以下结果。

Theorem 2.9 (Lucas检测的放宽版本) 设 \(N+1=RF\)，\((R,F)=1\) 且 \(R<F\)，有素因子分解 \(F=\prod\limits_{j=1}^n q_j^{\beta_j}\)。若有 \(\{U_k\}\) 为 Lucas 序列，\((2QD,N)=1\)，满足 \[(U_{(N+1)/q_j},N)=1,\qquad \forall j=1,\ldots,n\]且 \[U_{N+1}\equiv0\pmod{N}.\] 则 \(N\) 为素数。

Remark. Lucas 检测的一个优势在于 Lucas 序列可以通过递推快速地计算。设\[\begin{equation*} A_k= \begin{bmatrix} U_{k+1}&V_{k+1}\\ U_k & V_k \end{bmatrix}, \end{equation*}\]

则有\[\begin{equation*} A_k= \begin{bmatrix} P & -Q\\ 1 & 0\\ \end{bmatrix}A_{k-1}=\cdots= \begin{bmatrix} P & -Q\\ 1 & 0\\ \end{bmatrix}^kA_0. \end{equation*}\]可以使用快速求幂的方法在 \(O(\log k)\) 步中完成序列的计算。

Remark. 上述基于 \(N+1\) 分解的算法对 Mersenne素数 \(2^n-1\) 尤其简单，因此也被著名的 GIMPS (Great Internet Mersenne Prime Search) 所采用。目前为止已知的最大的 Mersenne 素数是 GIMPS 计划在 2008 年 8 月 23 日找到的第 45 个 Mersenne 素数，共有 12978189 个十进制位。有趣的是，2009 年 4 月 12 日找到的第 47 个 Mersenne 素数要比第 45 个来的小。

Lucas-Lehmer检测

Theorem 2.10 (对 Mersenne 素数的 Lucas-Lehmer 检测) 设 \(n\) 为奇数，\(v_0=4\)，\(v_k=v_{k-1}^2-2\)。则 \(M_n=2^n-1\) 为素数当且仅当 \[v_{n-2}\equiv0\pmod{M_n}.\]

Proof. 证明主要部分来源于定理 Theorem 2.8 ，然而仍有一些技术上的区别，这里就不赘述了。完整的可见 Lehmer 在 1930 的证明 (Lehmer 1930)。另外 J.W.Bruce 在 1993 年给出了一个短至 2 页的 “trival” 版证明 (Bruce 1993)。

2.5 概率性的检测方法

更加富有趣味的是素性的 概率性检测方法。Knuth (Knuth 1997) 这样评价概率性的算法：“与其说算法重复地猜测错，倒不如说由于硬件的失灵或宇宙射线的原因，我们的计算机在它的计算中丢了一位。” 概率性的算法使我们对传统的可靠性产生疑问：我们是否真的需要”素性”的严格确证？概率性算法最早由 Solovay，Strassen (Solovay and Strassen 1977) 于 1974 年提出，Rabin-Miller 的改进方法为 Mathematica 软件所采用。Baillie-PSW 检测则综合了各种概率性检测方法，目前为止仍没有找到失败的反例，并且已经验证检测对于 \(10^{15}\) 以下的整数均是正确的。

2.5.1 Solovay-Strassen检测

Solovay-Strassen检测

Definition 2.10 (算法：Solovay-Strassen检测)  

  1. 随机生成满足 \(1\le a\le N\) 的整数 \(a\)；
  2. 若 \((a,N)=1\) 且 \(\jacobi{a}{N}\equiv a^{(N-1)/2}\pmod{N}\)， 则输出 \(N\) 为素数，否则输出 \(N\) 可能为合数。

Theorem 2.11 算法 Definition 2.10 重复执行 \(k\) 次，给出错误的概率为 0（当 \(N\) 为素数时）或 \(2^{-k}\)（当 \(N\) 为合数时）

Proof. 只需证明当 \(N\) 为合数，\((a,N)=1\) 时，\(\jacobi{a}{N}\equiv a^{(N-1)/2}\pmod{N}\) 的概率不超过 \(\frac{1}{2}\) 即可。设\[G=\left\{a+N\mathbb{Z}\bigm|a\in\mathbb{Z},(a,N)=1,a^{(N-1)/2}\equiv\jacobi{a}{N}\pmod{N}\right\}.\]则 \(G<M_N\)，因此只需证明 \(G\ne M_N\) 即可。

如果 \(N\) 能分解为两个互素的非平凡因子 \(r\)，\(s\)，我们证明必有 \(\forall a\) 满足 \((a,N)=1\) 都有 \(a^{(N-1)/2}\equiv1\equiv\jacobi{a}{N}\pmod{N}\)（由 Jacobi 符号的性质便知这是不可能的）。若不然，由中国剩余定理找到 \(b\) 满足 \(b\equiv1\pmod{r}\) 且 \(b\equiv a\pmod{s}\)。则有 \(b^{(N-1)/2}\equiv 1\pmod{r}\) 且 \(b^{(N-1)/2}\equiv -1\pmod{s}\)，而这与 \(b^{(N-1)/2}\equiv\pm1\pmod{N}\) 是矛盾的！

如果 \(N=p^e\) 为素数幂，则 \(\forall a\) 满足 \((a,N)=1\) 都有 \(a^{p^e-1}\equiv1\pmod{p^e}\)，再由 Euler 定理知道 \(p^{e-1}(p-1)\mid p^e-1\)。而这也是不可能的。

2.5.2 Rabin-Miller检测

Solovay-Strassen 检测利用了 Euler 伪素数”并不多”的性质，使用随机给出的基 \(a\) 多次重复进而给出高成功率的素性检测结果。同样的想法也可以施用于强伪素数与 Lucas 伪素数，前者便是著名的 Rabin-Miller 检测，后者则被运用到 Baillie-PSW 检测中。

Rabin-Miller检测 可以看成我们在注 Remark 2.1 中的想法的一个具体化。

Definition 2.11 (算法：Rabin-Miller 强伪素数检测) 设 \(N-1=d\cdot 2^s\)，1. 随机生成满足 \(1\le a\le N\) 的整数 \(a\)；2. 顺次计算 \[a^d,a^{2d},a^{4d},\ldots,a^{2^s\cdot d}.\] 若计算到第 \(k\) 步时有1. \(k=1\) 且 \(a^d\equiv1\pmod{N}\)，输出 \(N\) 可能为素数；2. \(k>1\) 且 \(a^{2^{k-1}\cdot d}\equiv-1\pmod{N}\)，输出 \(N\) 可能为素数；3. \(k>s\)，输出 \(N\) 为合数。

Remark. Rabin (Rabin 1980) 证明了算法 Definition 2.11 重复 \(k\) 遍，给出正确判断的概率大于 \(1-4^{-k}\)。

Remark. 使用单个基 \(a\) 的 Rabin-Miller 检测可能会遗漏许多基 \(a\) 下的强伪素数，因此实践中的确需要使用多基的 Rabin-Miller 测试。例如使用前 7 个素数组成的多基 Rabin-Miller 测试，可以保证算法在 \(341550071728321\approx3.4\times10^{14}\) 以下均是有效的，而且这个数在用前 8 个素数为基的 Rabin-Miller 测试下没有改进。

2.5.3 Baillie-PSW检测

只是使用多基的 Rabin-Miller 测试可能得不到好的效率。Baillie (Baillie and Wagstaff 1980) 将基为 2 的 Rabin-Miller 检测与 Lucas 伪素数检测结合起来，得到更为有效的素数检测方法。Pomerance, Selfridge, Wagstaff 在 (Pomerance, Selfridge, and Wagstaff 1980) 中对小于 \(25\times10^9\) 的数验证了算法的正确性。尽管 Pomerance (Pomerance 1984) 指出对于充分大的 \(N\)，必定有 Baillie-PSW 检测的反例，并且以 30 美元悬赏找出一个算法失败的反例（后来增加到 620 美元），不过反例至今没有找到，并且有经验估计认为第一个反例如果被找到的话，至少得有 10000 个十进位长度（参见 (Martin 2004)）。

下面我们正式给出 Baillie-PSW检测。

Definition 2.12 (算法：Baillie-PSW检测)  

  1. 使用小素数试除 \(N\)，若能整除，输出 \(N\) 为合数。
  2. 使用基为 2 的 Rabin-Miller 强伪素数检测 Definition 2.11，若 \(N\) 非强伪素数，输出 \(N\) 为合数。
  3. 选择以下两种方法之一确定 Lucas 序列的参数 \(P\)，\(Q\)：
    • (Selfridge 建议) 取 \(D\) 为 \(5,-7,9,-11,13,\ldots\) 中使得 \(\legendre{D}{N}=-1\) 的第一个数，选择 \(P=1\)，\(Q=\frac{1-D}{4}\)；
    • (Baillie 建议) 取 \(D\) 为 \(5,9,13,17,21,\ldots\) 中使得 \(\legendre{D}{N}=-1\) 的第一个数，选择 \(P\) 为 \(>\sqrt{D}\) 的最小奇数，\(Q=\frac{P^2-D}{4}\)。
  4. 使用 \(P\)，\(Q\) 为参数的 Lucas 伪素数检测算法 Definition 2.9，若 \(N\) 非 Lucas 伪素数，输出 \(N\) 为合数，否则输出 \(N\) 可能为合数。 用算法 Definition 4.7 检测 \(N\) 是否为完全平方数。

Remark. 由于 \(D=P^2-4Q^2\)，只需尝试模 4 余 1 的数。Selfridge 建议方法中不使用 \(-3\) 是因为当 \(D=-3\) 时有 \(P=Q=1\)，将会产生以 \(\{1,1,0,-1,-1,0\}\) 为循环节的周期 Lucas 序列，这将使得每个奇合数变成关于 \(P,Q\) 的 Lucas 伪素数，并非我们所想要的。

Remark. 若第三步中尝试过程中计算出前若干个 \(\legendre{D}{N}\) 均为 1，则 \(N\) 很可能为完全平方数，此时可用算法 Definition 4.7 对 \(N\) 进行平方检测以防止额外的计算，若 \(N\) 不是平方数则继续寻找 \(D\) 的过程。另外尝试过程中若计算得 \(\legendre{D}{N}=0\)，则意味着 \(N\) 必为合数，可直接终止计算。

Remark. (Baillie and Wagstaff 1980) 证明了，在第三步中，两种方法取到合适的 \(D\) 的平均尝试次数小于 \(2\)。