卢卡斯-莱默检验法

Template:NoteTA 卢卡斯-莱默检验法（Template:Lang-en），是数学中检验梅森数的素性检验，由法國數學家爱德华·卢卡斯（Template:Lang）于1878年完善，美國數學家德里克·亨利·莱默（Template:Lang）随后于1930年代将其改进。

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

方法

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

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

$s_i=\{\begin{array}{c}4\\ s_{i-1}^2-2\end{array}$	，如果$i=0$；
	，如果$i>0$。

.

.

.

这个序列的开始几项是4, 14, 194, 37634, ... Template:OEIS

那么M_p是素数当且仅当

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

正确性的证明

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

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

$\begin{array}{ccc}{s}_n& =& s_{n-1}^2-2\\ & =& {({\omega }^{2^{n-1}}+{\overline{\omega }}^{2^{n-1}})}^2-2\\ & =& {\omega }^{2^n}+{\overline{\omega }}^{2^n}+2(\omega \overline{\omega }{)}^{2^{n-1}}-2\\ & =& {\omega }^{2^n}+{\overline{\omega }}^{2^n},\end{array}$

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

充分性

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

假设$s_{p-2}\equiv 0(\mathrm{mod}{M}_p)$。那么对于某个整数k，有${\omega }^{2^{p-2}}+{\overline{\omega }}^{2^{p-2}}=k{M}_p$，以及：

$\begin{array}{ccc}{\omega }^{2^{p-2}}& =& k{M}_p-{\overline{\omega }}^{2^{p-2}}\\ {\left({\omega }^{2^{p-2}}\right)}^2& =& k{M}_p{\omega }^{2^{p-2}}-(\omega \overline{\omega }{)}^{2^{p-2}}\\ {\omega }^{2^{p-1}}& =& k{M}_p{\omega }^{2^{p-2}}-1.(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)\text{ mod }q]+[(bc+ad)\text{ mod }q]\sqrt{3}$.

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

现在，由于$M_p\equiv 0(\mathrm{mod}q)$，且$\omega \in X$，我们有$k{M}_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}}\ne 1$，因此这个阶不能整除$2^{p-1}$。由于群元素的阶最多就是群的大小，我们便得出结论，$2^p\le q^2-1<q^2$。但由于q是$M_p$的一个非平凡素因子，我们必须有$q^2\le M_p=2^p-1$，得出矛盾$2^p<2^p-1$。因此$M_p$是素数。

必要性

我们假设$M_p$是素数，欲推出$s_{p-2}\equiv 0(\mathrm{mod}{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(\mathrm{mod}{M}_p)$.

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

$2^{(M_p-1)/2}\equiv 1(\mathrm{mod}{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}(\mathrm{mod}{M}_p)$

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

$a^{M_p}\equiv a(\mathrm{mod}{M}_p)$

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

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

$\begin{array}{ccc}(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}$

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

$\begin{array}{ccc}{\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(\mathrm{mod}4)$，我们还需要做的就是把方程的两边乘以${\overline{\omega }}^{(M_p+1)/4}$，并利用$\omega \overline{\omega }=1$：

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

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

参见

• 梅森素数
• 因特网梅森素数大搜索（GIMPS）
• 新梅森猜想
• 埃拉托斯特尼筛法
• 米勒-拉宾检验
• 试除法
• 费马素性检验
• 卢卡斯-莱默检验法
• 孪生素数
• 三胞胎素数
• 四胞胎素数
• 素数判定法则
• 表兄弟素数
• 六素数
• X²+1素数

参考文献

• Template:Cite book Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

外部链接

• Template:MathWorld
• GIMPS (The Great Internet Mersenne Prime Search)Template:Wayback
• A proof of Lucas–Lehmer–Reix test (for Fermat numbers) Template:Wayback
• Lucas–Lehmer test at MersenneWiki