卢卡斯-莱默检验法

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

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

方法

卢卡斯-莱默检验法原理是这样:
令梅森数 Mp = 2p− 1作为检验对象(预设p素数,否则Mp就是合数了)。

定义序列{si }:所有的i ≥ 0

  ,如果 
,如果 
.
.
.

这个序列的开始几项是4, 14, 194, 37634, ... (OEIS数列A003010

那么Mp是素数当且仅当

 

否则, Mp合数
sp − 2Mp的余数叫做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,都有 

 
 

最后一个步骤可从 推出。在两个部分中,我们都将用到这个结果。

充分性

我们希望证明 意味着 是素数。我们叙述一个利用初等群论的证明,由J. W.布鲁斯给出[2]

假设 。那么对于某个整数k,有 ,以及:

 

现在假设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*为 的乘法群。我们将用到以下的引理:

 

(根据费马小定理),以及

 

对于所有整数a(费马小定理)。

那么,在群X*中,我们有:

 

简单计算可知  。我们可以用这个结果来计算群X*中的 

 

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

 

由于 ,我们还需要做的就是把方程的两边乘以 ,并利用 

 

由于sp−2是整数,且在X*内是零,因此它也是零mod Mp

参见

注释

  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.  ) Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

外部链接