卢卡斯-莱默检验法

数学中，卢卡斯-莱默检验法是检验梅森数的素性检验，是由爱德华·卢卡斯于1878年完善，德里克·亨利·莱默随后于1930年代将其改进。

因特网梅森素数大搜索用这个检验法找到了不少很大的素数，最近几个最大的素数就是这个项目发现的。由于梅森数比随机选择的整数更有可能是素数，因此他们认为这是一个极有用的方法。

方法

卢卡斯－莱默检验法原理是这样：令梅森数 M_p = 2^p− 1 作为检验对象（预设p是素数, 否则M_p 就是合数了）。 定义序列 {s_i }：所有的i ≥ 0

$s_i =\begin{cases}\;\;\,4 \\s_{i-1}^2-2 \end{cases}$	，如果 $\displaystyle i = 0$；
	，如果 $\displaystyle i > 0$。

.

.

.

这个序列的开始几项是4, 14, 194, 37634, ... （OEIS中的数列A003010） 那么M_p 是素数 当且仅当

$s_{p-2}\equiv0\pmod{M_p};$

否则, M_p 是合数。 s_{p − 2} 模 M_p 的余数叫做 p 的卢卡斯－莱默余数。

例子

假设我们想验证M₃ = 7是素数。我们从s=4开始，并更新3−2 = 1次，把所有的得数模7：

• s ← ((4 × 4) − 2) mod 7 = 0

由于我们最终得到了一个能被7整除的s，因此M₃是素数。

另一方面，M₁₁ = 2047 = 23 × 89就不是素数。我们仍然从s=4开始，并更新11−2 = 9次，把所有的得数模2047：

• s ← ((4 × 4) − 2) mod 2047 = 14
• s ← ((14 × 14) − 2) mod 2047 = 194
• s ← ((194 × 194) − 2) mod 2047 = 788
• s ← ((788 × 788) − 2) mod 2047 = 701
• s ← ((701 × 701) − 2) mod 2047 = 119
• s ← ((119 × 119) − 2) mod 2047 = 1877
• s ← ((1877 × 1877) − 2) mod 2047 = 240
• s ← ((240 × 240) − 2) mod 2047 = 282
• s ← ((282 × 282) − 2) mod 2047 = 1736

由于s最终仍未能被2047整除，因此M₁₁=2047不是素数。但是，我们从这个检验法仍然无法知道2047的因子，只知道它的卢卡斯-莱默余数1736。

正确性的证明

我们注意到${\langle}s_i{\rangle}$是一个具有闭式解的递推关系。定义$\omega = 2 + \sqrt{3}$及$\bar{\omega} = 2 - \sqrt{3}$；我们可以用数学归纳法来验证对于所有i，都有$s_i = \omega^{2^i} + \bar{\omega}^{2^i}$：

$s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.$

$\begin{array}{lcl}s_n & = & s_{n-1}^2 - 2 \\ & = & \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\ & = & \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\ & = & \omega^{2^n} + \bar{\omega}^{2^n}, \\ \end{array}$

最后一个步骤可从$\omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1$推出。在两个部分中，我们都将用到这个结果。

充分性

我们希望证明$s_{p-2}\equiv0\pmod{M_p}$意味着$M_p$是素数。我们叙述一个利用初等群论的证明，由J. W. 布鲁斯给出。

假设$s_{p-2} \equiv 0 \pmod{M_p}$。那么对于某个整数k，有$\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p$，以及：

$\begin{array}{rcl} \omega^{2^{p-2}} & = & kM_p - \bar{\omega}^{2^{p-2}} \\ \left(\omega^{2^{p-2}}\right)^2 & = & kM_p\omega^{2^{p-2}} - (\omega\bar{\omega})^{2^{p-2}} \\ \omega^{2^{p-1}} & = & kM_p\omega^{2^{p-2}} - 1.\quad\quad\quad\quad\quad(1) \\ \end{array}$

现在假设M_p是合数，其非平凡素因子q > 2（所有梅森素数都是奇数）。定义含有q²个元素的集合$X = \{a + b\sqrt{3} | a, b \in \mathbb{Z}_q\}$，其中$\mathbb{Z}_q$是模q的整数，是一个有限域。X中的乘法运算定义为：

$(a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}$.

由于q > 2，因此$\omega$和$\bar{\omega}$位于X内。任何两个位于X内的数的乘积也一定位于X内，但它不是一个群，因为不是所有的元素x都有逆元素y，使得xy = 1。如果我们只考虑有逆元素的元素，我们便得到了一个群X*，它的大小最多为$q^2-1$（因为0没有逆元素）。

现在，由于$M_p \equiv 0 \pmod q$，且$\omega \in X$，我们有$kM_p\omega^{2^{p-2}} = 0$，根据方程(1)可得$\omega^{2^{p-1}} = -1$。两边平方，得$\omega^{2^p} = 1$，证明了$\omega$是可逆的，其逆元素为$\omega^{2^{p}-1}$，因此位于X*内，它的目能整除$2^p$。实际上，这个目必须等于$2^p$，因为$\omega^{2^{p-1}} \neq 1$，因此这个目不能整除$2^{p-1}$。由于群元素的目最多就是群的大小，我们便得出结论，$2^p \leq q^2 - 1 < q^2$。但由于q是$M_p$的一个非平凡素因子，我们必须有$q^2 \leq M_p = 2^p-1$，得出矛盾$2^p < 2^p-1$。因此$M_p$是素数。

必要性

我们假设$M_p$是素数，欲推出$s_{p-2} \equiv0\pmod{M_p}$。我们叙述一个Öystein J. R. Ödseth的证明。首先，注意到3是模 M_p的二次非剩余，这是因为对于奇数p > 1，2 ^p − 1只取得值7 mod 12，因此从勒让德符号的性质可知$(3|M_p)$是−1。根据欧拉准则，可得：

$3^{(M_p-1)/2} \equiv -1 \pmod{M_p}$.

另一方面，2是模$M_p$的二次剩余，这是因为$2^p \equiv 1 \pmod{M_p}$，因此$2 \equiv 2^{p+1} = \left(2^{(p+1)/2}\right)^2 \pmod{M_p}$。根据欧拉准则，可得：

$2^{(M_p-1)/2} \equiv 1 \pmod{M_p}$.

接着，定义$\sigma = 2\sqrt{3}$，并像前面那样，定义X*为$\{a + b\sqrt{3} | a, b \in \mathbb{Z}_{M_p}\}$的乘法群。我们将用到以下的引理：

$(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}$

（根据费马小定理），以及

$a^{M_p} \equiv a \pmod{M_p}$

对于所有整数a（费马小定理）。

那么，在群X*中，我们有：

$\begin{array}{lcl} (6+\sigma)^{M_p} & = & 6^{M_p} + (2^{M_p})(\sqrt{3}^{M_p}) \\ & = & 6 + 2(3^{(M_p-1)/2})\sqrt{3} \\ & = & 6 + 2(-1)\sqrt{3} \\ & = & 6 - \sigma. \end{array}$

我们选择$\sigma$，使得$\omega = (6+\sigma)^2/24$。我们可以用这个结果来计算群X*中的$\omega^{(M_p+1)/2}$：

$\begin{array}{lcl} \omega^{(M_p+1)/2} & = & (6 + \sigma)^{M_p+1}/24^{(M_p+1)/2} \\ & = & (6 + \sigma)^{M_p}(6 + \sigma)/(24 \times 24^{(M_p-1)/2}) \\ & = & (6 - \sigma)(6 + \sigma)/(-24) \\ & = & -1. \end{array}$

其中我们用到了以下的事实：

$24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.$

由于$M_p \equiv 3 \pmod 4$，我们还需要做的就是把方程的两边乘以$\bar{\omega}^{(M_p+1)/4}$，并利用$\omega\bar{\omega}=1$：

$\begin{array}{rcl} \omega^{(M_p+1)/2}\bar{\omega}^{(M_p+1)/4} & = & -\bar{\omega}^{(M_p+1)/4} \\ \omega^{(M_p+1)/4} + \bar{\omega}^{(M_p+1)/4} & = & 0 \\ \omega^{(2^p-1+1)/4} + \bar{\omega}^{(2^p-1+1)/4} & = & 0 \\ \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} & = & 0 \\ s_{p-2} & = & 0. \\ \end{array}$

由于s_p−2是整数，且在X*内是零，因此它也是零mod M_p。

参见

• 梅森素数
• 因特网梅森素数大搜索 (GIMPS)
• 新梅森猜想
• 埃拉托斯特尼筛法
• 米勒-拉宾检验
• 试除法
• 费马素性检验

参考文献

• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective 1st edition. Springer. 2001. ISBN 0387947779.  Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

外部链接

• MathWorld：卢卡斯-莱默检验法
• GIMPS
• 卢卡斯-莱默检验法的证明