数学中,卢卡斯-莱默检验法(英語:Lucas–Lehmer primality test)是检验梅森数的素性检验,是由爱德华·卢卡斯于1878年完善,德里克·亨利·莱默随后于1930年代将其改进。
因特网梅森素数大搜索用这个检验法找到了不少很大的素数,最近几个最大的素数就是这个项目发现的。[1]由于梅森数比随机选择的整数更有可能是素数,因此他们认为这是一个极有用的方法。
卢卡斯-莱默检验法原理是这样:
令梅森数
Mp = 2p− 1作为检验对象(预设p是素数,否则Mp就是合数了)。
定义序列{si }:所有的i ≥ 0
|
,如果 ;
|
,如果 。
|
- .
- .
- .
这个序列的开始几项是4, 14, 194, 37634, ... (OEIS數列A003010)
那么Mp是素数当且仅当
![{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/927bf8c53e8606aee46b2aa67843462e2dc0dfce)
否则, Mp是合数。
sp − 2模Mp的余数叫做p的卢卡斯-莱默余数。
假设我们想验证M3 = 7是素数。我们从s=4开始,并更新3−2 = 1次,把所有的得数模7:
- s ← ((4×4) − 2) mod 7 = 0
由于我们最终得到了一个能被7整除的s,因此M3是素数。
另一方面,M11 = 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整除,因此M11=2047不是素数。但是,我们从这个检验法仍然无法知道2047的因子,只知道它的卢卡斯-莱默余数1736。
正确性的证明[编辑]
我们注意到
是一个具有闭式解的递推关系。定义
及
;我们可以用数学归纳法来验证对于所有i,都有
:
。
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/326a6e6398dffcc03228d560068101f83680e12c)
最后一个步骤可从
推出。在两个部分中,我们都将用到这个结果。
充分性[编辑]
我们希望证明
意味着
是素数。我们叙述一个利用初等群论的证明,由J. W.布鲁斯给出[2]。
假设
。那么对于某个整数k,有
,以及:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fd3fd20a6f31a5ef5dfc1f173e1abcfeba52c18)
现在假设Mp是合数,其非平凡素因子q > 2(所有梅森素数都是奇数)。定义含有q2个元素的集合
,其中
是模q的整数,是一个有限域。X中的乘法运算定义为:
.
由于q > 2,因此
和
位于X内。任何两个位于X内的数的乘积也一定位于X内,但它不是一个群,因为不是所有的元素x都有逆元素y,使得xy = 1。如果我们只考虑有逆元素的元素,我们便得到了一个群X*,它的大小最多为
(因为0没有逆元素)。
现在,由于
,且
,我们有
,根据方程(1)可得
。两边平方,得
,证明了
是可逆的,其逆元素为
,因此位于X*内,它的目能整除
。实际上,这个阶必须等于
,因为
,因此这个阶不能整除
。由于群元素的阶最多就是群的大小,我们便得出结论,
。但由于q是
的一个非平凡素因子,我们必须有
,得出矛盾
。因此
是素数。
必要性[编辑]
我们假设
是素数,欲推出
。我们叙述一个Öystein J. R.
Ödseth的证明[3]。首先,注意到3是模 Mp的二次非剩余,这是因为对于奇数p > 1,2 p − 1只取得值7 mod 12,因此从勒让德符号的性质可知
是−1。根据欧拉准则,可得:
.
另一方面,2是模
的二次剩余,这是因为
,因此
。根据欧拉准则,可得:
.
接着,定义
,并像前面那样,定义X*为
的乘法群。我们将用到以下的引理:
![{\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/201dfd84053e5e181725159e9c9dc472c27668a6)
(根据费马小定理),以及
![{\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bf4c4d54cefab92adb2e98a7489f76529e99729)
对于所有整数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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2f4bb5cc6bfa06eec09e64a303ddd3cde0459e)
简单计算可知
。我们可以用这个结果来计算群X*中的
:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a6f18bf219de984b98bf12269fe3f6d713b185d)
其中我们用到了以下的事实:
。
由于
,我们还需要做的就是把方程的两边乘以
,并利用
:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82616dbe232d8dce78037b823f02f80851a81b04)
由于sp−2是整数,且在X*内是零,因此它也是零mod Mp。
- ^ GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what (页面存档备份,存于互联网档案馆)
- ^ 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.
- ^ Ö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 (页面存档备份,存于互联网档案馆)
参考文献[编辑]
外部链接[编辑]