查看“︁卢卡斯-莱默检验法”︁的源代码

{{noteTA|T=zh-cn:卢卡斯-莱默检验法;zh-tw:盧卡斯-萊默質數判定法;zh-hk:盧卡斯-萊默質數判定法;|1=zh-cn:卢卡斯-莱默检验法;zh-tw:盧卡斯-萊默質數判定法;zh-hk:盧卡斯-萊默質數判定法;|G1=Math}}
'''卢卡斯-莱默检验法'''（{{lang-en|Lucas–Lehmer primality test}}），是[[数学]]中检验[[梅森数]]的[[素性检验]]，由法國數學家[[爱德华·卢卡斯]]（{{lang|fr|Édouard Lucas}}）于1878年完善，美國數學家[[德里克·亨利·莱默]]（{{lang|en|Derrick Henry Lehmer}}）随后于1930年代将其改进。

[[GIMPS|因特网梅森質数大搜索]]用这个检验法找到了不少很大的[[質数]]，最近几个最大的質数就是这个项目发现的。<ref>GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what {{Wayback|url=http://www.mersenne.org/faq.htm#what |date=20080923070539 }}</ref>由于梅森数比随机选择的整数更有可能是質数，因此他们认为这是一个极有用的方法。

==方法==

卢卡斯－莱默检验法原理是这样：<br>
令梅森数
''M''<sub>''p''</sub> = 2<sup>''p''</sup>− 1作为检验对象（预设''p''是質数，否则''M''<sub>''p''</sub>就是[[合数]]了）。<br>

定义序列{''s''<sub>''i''</sub> }：所有的''i'' ≥ 0 
::{| align=left border="0"
|rowspan=2| <math> s_i =\begin{cases}\;\;\,4 \\s_{i-1}^2-2 \end{cases}</math>
| ，如果<math>\displaystyle i = 0</math>；
|-
| ，如果<math>\displaystyle i > 0</math>。
|}
:.
:.
:.

这个序列的开始几项是[[4]], [[14]], [[194]], [[37634]], ... {{OEIS|id=A003010}}<br>

那么''M''<sub>''p''</sub>是素数[[当且仅当]]<br>

:<math>s_{p-2}\equiv0\pmod{M_p};</math><br>

否则, ''M''<sub>''p''</sub>是[[合数]]。<br>
''s''<sub>''p'' − 2</sub>模''M''<sub>''p''</sub>的余数叫做''p''的'''卢卡斯－莱默余数'''。

==例子==

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

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

由于我们最终得到了一个能被7整除的''s''，因此M<sub>3</sub>是素数。

另一方面，M<sub>11</sub> = 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<sub>11</sub>=2047不是素数。但是，我们从这个检验法仍然无法知道2047的因子，只知道它的卢卡斯-莱默余数1736。

==正确性的证明==

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

:<math>s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4</math>。
:<math>\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}</math>
最后一个步骤可从<math>\omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1</math>推出。在两个部分中，我们都将用到这个结果。

===充分性===

我们希望证明<math>s_{p-2}\equiv0\pmod{M_p}</math>意味着<math>M_p</math>是素数。我们叙述一个利用初等[[群论]]的证明，由J. W.布鲁斯给出<ref>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.</ref>。 

假设<math>s_{p-2} \equiv 0 \pmod{M_p}</math>。那么对于某个整数''k''，有<math>\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p</math>，以及：
:<math>\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}</math>

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

:<math>(a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}</math>.

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


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

===必要性===

我们假设<math>M_p</math>是素数，欲推出<math>s_{p-2} \equiv0\pmod{M_p}</math>。我们叙述一个Öystein J. R.
Ödseth的证明<ref>Ö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 {{Wayback|url=http://www.uib.no/People/nmaoy/papers/luc.pdf |date=20110606101253 }}</ref>。首先，注意到3是模 ''M''<sub>''p''</sub>的[[二次剩余|二次非剩余]]，这是因为对于奇数''p'' > 1，2<sup> ''p''</sup> − 1只取得值7 mod 12，因此从[[勒让德符号]]的性质可知<math>(3|M_p)</math>是−1。根据[[欧拉准则]]，可得：

: <math>3^{(M_p-1)/2} \equiv -1 \pmod{M_p}</math>.

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

: <math>2^{(M_p-1)/2} \equiv 1 \pmod{M_p}</math>.

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

: <math>(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}</math>

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

: <math>a^{M_p} \equiv a \pmod{M_p}</math>

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

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

:<math>\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}</math>

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

:<math>\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}</math>

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

: <math>24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1</math>。

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

: <math>\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}</math>

由于''s''<sub>''p''−2</sub>是整数，且在''X''*内是零，因此它也是零mod ''M''<sub>''p''</sub>。

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

==注释==
<references />

==参考文献==
* {{cite book|author = [[Richard Crandall]] and [[Carl Pomerance]] | year = 2001 | title = Prime Numbers: A Computational Perspective | publisher = Springer | edition = 1st edition | id = ISBN 978-0-387-94777-8}} Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

== 外部链接 ==
* {{MathWorld |urlname=Lucas-LehmerTest |title=卢卡斯-莱默检验法}}
* [http://www.mersenne.org GIMPS (The Great Internet Mersenne Prime Search)]{{Wayback|url=http://www.mersenne.org/ |date=20180403133811 }}
* [https://arxiv.org/abs/0705.3664 A proof of Lucas–Lehmer–Reix test (for Fermat numbers)] {{Wayback|url=https://arxiv.org/abs/0705.3664 |date=20180510185223 }}
* [https://web.archive.org/web/20160216234138/http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test Lucas–Lehmer test] at MersenneWiki

{{数论算法}}

[[Category:素性测试]]
[[Category:梅森素数]]