卢卡斯-莱默检验法

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

方法[编辑]

卢卡斯-莱默检验法原理是这样:令梅森数 Mp = 2p− 1 作为检验对象(预设p素数, 否则Mp 就是合数了)。 定义序列 {si }:所有的i ≥ 0

 s_i =\begin{cases}\;\;\,4 \\s_{i-1}^2-2 \end{cases} ,如果 \displaystyle i = 0
,如果 \displaystyle i > 0
.
.
.

这个序列的开始几项是4, 14, 194, 37634, ... (OEIS中的数列A003010) 那么Mp 是素数 当且仅当

s_{p-2}\equiv0\pmod{M_p};

否则, 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。

正确性的证明[编辑]

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

s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.
\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}

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

充分性[编辑]

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

假设s_{p-2} \equiv 0 \pmod{M_p}。那么对于某个整数k,有\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p,以及:

\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}

现在假设Mp是合数,其非平凡素因子q > 2(所有梅森素数都是奇数)。定义含有q2个元素的集合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) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}.

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

现在,由于M_p \equiv 0 \pmod q,且\omega \in X,我们有kM_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}} \neq 1,因此这个阶不能整除2^{p-1}。由于群元素的阶最多就是群的大小,我们便得出结论,2^p \leq q^2 - 1 < q^2。但由于qM_p的一个非平凡素因子,我们必须有q^2 \leq M_p = 2^p-1,得出矛盾2^p < 2^p-1。因此M_p是素数。

必要性[编辑]

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

3^{(M_p-1)/2} \equiv -1 \pmod{M_p}.

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

2^{(M_p-1)/2} \equiv 1 \pmod{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} \pmod{M_p}

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

a^{M_p} \equiv a \pmod{M_p}

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

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

\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}

我们选择\sigma,使得\omega = (6+\sigma)^2/24。我们可以用这个结果来计算群X*中的\omega^{(M_p+1)/2}

\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}

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

24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.

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

\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}

由于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

参考文献[编辑]

外部链接[编辑]