卢卡斯-莱默检验法

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

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

方法

卢卡斯－莱默检验法原理是这样：
令梅森数 M_p = 2^p− 1作为检验对象（预设p是素数，否则M_p就是合数了）。

定义序列{s_i }：所有的i ≥ 0

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

.

.

.

这个序列的开始几项是4, 14, 194, 37634, ... （OEIS數列A003010）

那么M_p是素数当且仅当

${\displaystyle s_{p-2}\equiv 0{\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。

正确性的证明

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

${\displaystyle s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=(2+{\sqrt {3}})+(2-{\sqrt {3}})=4}$ 。

${\displaystyle {\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}}}$ 

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

充分性

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

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

${\displaystyle {\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²个元素的集合${\displaystyle X=\{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{q}\}}$ ，其中${\displaystyle \mathbb {Z} _{q}}$ 是模q的整数，是一个有限域。X中的乘法运算定义为：

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

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

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

必要性

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

${\displaystyle 3^{(M_{p}-1)/2}\equiv -1{\pmod {M_{p}}}}$ .

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

${\displaystyle 2^{(M_{p}-1)/2}\equiv 1{\pmod {M_{p}}}}$ .

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

${\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}$ 

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

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$ 

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

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

${\displaystyle {\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}}}$ 

简单计算可知 ${\displaystyle \omega =(6+\sigma )^{2}/24}$ 。我们可以用这个结果来计算群X*中的${\displaystyle \omega ^{(M_{p}+1)/2}}$ ：

${\displaystyle {\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}}}$ 

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

${\displaystyle 24^{(M_{p}-1)/2}=(2^{(M_{p}-1)/2})^{3}(3^{(M_{p}-1)/2})=(1)^{3}(-1)=-1}$ 。

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

${\displaystyle {\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）
• 新梅森猜想
• 埃拉托斯特尼筛法
• 米勒-拉宾检验
• 试除法
• 费马素性检验
• 卢卡斯-莱默检验法
• 孪生素数
• 三胞胎素数
• 四胞胎素数
• 素数判定法则
• 表兄弟素数
• 六素数
• X²+1素数

注释

1. GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what （页面存档备份，存于互联网档案馆）
2. J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. The American Mathematical Monthly, Vol.100, No.4, pp.370–371. April 1993.
3. Öystein J. R. Ödseth. A note on primality tests for N = h · 2n − 1. Department of Mathematics, University of Bergen. http://www.uib.no/People/nmaoy/papers/luc.pdf （页面存档备份，存于互联网档案馆）

参考文献

• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective 1st edition. Springer. 2001. ISBN 978-0-387-94777-8.  引文格式1维护：冗余文本 (link) Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

外部链接

• 埃里克·韦斯坦因. 卢卡斯-莱默检验法. MathWorld. 
• GIMPS (The Great Internet Mersenne Prime Search)（页面存档备份，存于互联网档案馆）
• A proof of Lucas–Lehmer–Reix test (for Fermat numbers) （页面存档备份，存于互联网档案馆）
• at MersenneWiki