素数判定

Solovay-Strassen检测
Rabin-Miller检测
Baillie-PSW检测

素数判定(the Recognition of Primes)是一个数论中十分基本,却又趣味盎然的问题.判定一个整数是否是素数,最为朴素的想法是直接利用素数的定义,用小的素数去一一试除,如果能整除的话,那就能确定无疑为合数了.统计表明,大约有76%的奇数有小于100的素因子,可见这种最平凡的方法有时十分有效.

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

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

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

Fermat检测

几乎所有素数检测的想法之基石均为著名的Fermat小定理,即若 $p$ 为素数, $(a,p)=1$ ,则 $a^{p-1}\equiv1\pmod{p}.$

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

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

定义1(Fermat伪素数) 满足 $a^{N-1}\equiv1\pmod{N}$ 的合数 $N$ 称为一个(对于基 $a$ )的Fermat伪素数.

在 $25\times10^9$ 以下,有21853个对于基 $a=2$ 的Fermat伪素数[7],如果对其再进行基为 $a=3$ 的检测的话,伪素数将还剩下4709个,对于 $a=2,3,5$ 有2552个, $a=2,3,5,7$ 有1770个.

运用Fermat检测的关键是如何快速计算 $a^{d} \mod N$ .求幂运算采取二进算法1,2,可以使用Fermat检测的算法复杂度降到平均 $1.5\log N\cdot M(N)$ (其中 $M(N)$ 表示乘法运算的复杂度),已经为多项式阶的算法了. 使用Montgomery约化算法3可以更进一步地提高速度。

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

定义2(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伪素数)

Euler检测

Euler检测基于Euler的二次剩余定理,即若 $p$ 为奇素数, $(a,p)=1$ ,则 $a^{(p-1)/2}\equiv\legendre{a}{p}\pmod{p}.$ 其中 $\legendre{a}{p}$ 是Legendre符号.

算法2(Euler判则作为合性检测)

设 $N$ 为奇数,任取整数 $a$ ，满足 $(a,N)=1$ ：

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

定义3(Euler伪素数) 如果合数 $N$ , $(a,N)=1$ ,满足 $a^{(N-1)/2}\equiv\legendre{a}{N}\pmod{N}$ ,则称 $N$ 为(对于基 $a$ 的)Euler伪素数.

定义4(强伪素数) 设 $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}.$

注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的强伪素数.

注2 [7]证明了,Euler伪素数必定是强伪素数.

Lehmer $N-1$ 型检测

有时候 $N$ 的素性很难判定,而 $N\pm1$ 的分解却很容易得到.这一节的方法便是依赖于 $N-1$ 的素因子分解.

定理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,$ 且 $\begin{equation*} \tag{1} a^{N-1}\equiv1 \pmod{N} . \end{equation*}$ 则 $N$ 为素数.

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

注3 这里不要 $(a,N)=1$ 的条件,是因为其已经被包括在式(1)之中了.

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

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

定理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$ 为素数.

证明设 $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\mid \varphi(N) \Rightarrow \varphi(N)=N-1$ . □

注4 这个方法对 $M_N$ 的生成元很大的时候非常有用,因为我们不必找出一个“共同”的 $a$ 来.

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

证明用定理1即可,只需注意到3必为 $12n\pm 5$ 型素数的二次非剩余. □

注5 使用这个方法,在1963年[8]证明了 $F_{14}$ (有4933个十进制位)是合数，尽管但现在为止还不知道其任何一个因子。

下面的定理让我们可以拥有不必完全分解 $N-1$ 的便利.

定理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$ 为素数.

证明设 $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}.$ 矛盾！ □

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

证明在定理4中令 $F=2^n$ 即得. □

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})$ 的代数整数环，我们熟知(参见[9]，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小定理的类比。

定理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*}$

证明设 $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*}$ 从而得到所要结论。 □

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

定义5(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.$

注6 由特征方程对应的递推关系,知道 $\{U_n\},\{V_n\}$ 均为 $\mathbb{Z}$ 中的序列.

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

证明由 $(Q,M)=1$ 知 $Q$ 模 $M$ 可逆，而 $ab=Q$ ，知 $ab\cdot Q^{-1}\equiv1\pmod{M}$ ，从而 $a,b$ 均模 $M$ 可逆。又 $a-b=\sqrt{D}$ ，而 $D^{\varphi(N)}\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}.$ 引理得证。 □

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

证明若 $\legendre{D}{N}=1$ ，则由定理6可知 $a^{p-1}\equiv b^{p-1}\equiv1\pmod{p}$ ，从而 $(ab^{-1})^{p-1}\equiv1\pmod{p}$ ，由引理1知 $U_{p-1}\equiv0\pmod{p}$ 。

若 $\legendre{D}{N}=-1$ ，则由定理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}$ ，由引理1知 $U_{p+1}\equiv0\pmod{p}$ ，这就完成了证明。 □

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

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

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

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

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

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

定理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$ 为素数.

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

与 $N-1$ 型检测完全类似还可以得到以下结果.

定理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$ 为素数.

注8 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*}$ 可以使用快速求幂的方法在 $\log k$ 步中完成序列的计算.

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

定理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}.$

证明证明主要部分来源于定理8,然而仍有一些技术上的区别,这里就不赘述了.完整的可见Lehmer在1930的证明[10].另外J.W.Bruce在1993年给出了一个短至2页"trival"版证明[11]. □

概率性的检测方法

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

Solovay-Strassen检测

算法4(Solovay-Strassen检测)

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

定理11 算法4重复执行 $k$ 次,给出错误的概率为0(当 $N$ 为素数时)或 $2^{-k}$ (当 $N$ 为合数时)

证明只需证明当 $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$ .而这也是不可能的. □

Rabin-Miller检测

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

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

算法5(Rabin-Miller强伪素数检测) 设 $N-1=d\cdot 2^s$ ,

随机生成满足 $1\le a\le N$ 的整数 $a$ ;
顺次计算若计算到第步时有
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$ 为合数.

注10 Rabin[14]证明了算法5重复 $k$ 遍,给出正确判断的概率 $>1-4^{-k}$ .

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

Baillie-PSW检测

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

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

算法6(Baillie-PSW检测)

使用小素数试除 $N$ ，若能整除，输出 $N$ 为合数。
使用基为2的Rabin-Miller强伪素数检测5，若 $N$ 非强伪素数，输出 $N$ 为合数。
选择以下两种方法之一确定Lucas序列的参数，：
- (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}$ 。
使用 $P$ ， $Q$ 为参数的Lucas伪素数检测算法3，若 $N$ 非Lucas伪素数，输出 $N$ 为合数，否则输出 $N$ 可能为合数。用算法5检测 $N$ 是否为完全平方数。

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

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

注14 [15]证明了，在第三步中，两种方法取到合适的 $D$ 的平均尝试次数 $<2$ 。

参考文献

[1]Manindra Agrawal and Neeraj Kayal and Nitin Saxena, PRIMES is in P, Annals of Mathematics 160 (2004), no.2, 781 – 793.

[2]Adleman, Leonard M. and Pomerance, Carl and Rumely, Robert S., On Distinguishing Prime Numbers from Composite Numbers, The Annals of Mathematics 117 (1983), no.1, 173--206.

[3]Cohen, H. and Lenstra, H. W., Jr., Primality Testing and Jacobi Sums, Mathematics of Computation 42 (1984), no.165, 297--330.

[4]S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 1986, 316 - 329.

[5]A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Mathematics of Computation 61 (1993), 29 - 68.

[6]Henri Cohen, A Course in Computational Algebraic Number Theory, Springer Verlag, 1993.

[7]Pomerance, Carl and Selfridge, J. L. and Wagstaff, Samuel S., Jr., The Pseudoprimes to $25 \cdot 10^9$, Mathematics of Computation 35 (1980), no.151, 1003--1026.

[8]J. L. Selfridge and A. Hurwitz, Fermat numbers and Mersenne numbers, Mathematics of Computation 18 (1964), 146-148.

[9]聂灵沼，丁石孙, 代数学引论, 高等教育出版社, 北京, 2000.

[10]Lehmer, D. H., An Extended Theory of Lucas' Functions, The Annals of Mathematics 31 (1930), no.3, 419--448.

[11]Bruce, J. W., A Really Trivial Proof of the Lucas-Lehmer Test, The American Mathematical Monthly 100 (1993), no.4, 370--371.

[12]Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997.

[13]R. Solovay and V. Strassen, A Fast Monte-Carlo Test for Primality, SIAM Journal on Computing 6 (1977), no.1, 84-85.

[14]Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12 (1980), no.1, 128-138.

[15]Robert Baillie and Samuel S. Wagstaff, Jr., Lucas Pseudoprimes, Mathematics of Computation 35 (1980), no.152, 1391 - 1417.

[16]Pomerance, Carl, Are There Counterexamples to the Baillie-PSW Primality Test?, 1984, http://www.pseudoprime.com/dopo.pdf.

[17]Martin, M., Re: Baillie-PSW - Which variant is correct?, 2004, http://groups.google.com/group/sci.crypt/msg/48ec324b9fc9f866.