盧卡斯-萊默檢驗法

盧卡斯-萊默檢驗法（Lucas–Lehmer primality test），是數學中檢驗梅森數的素性檢驗，由法國數學家愛德華·盧卡斯（Édouard Lucas）於1878年完善，美國數學家德里克·亨利·萊默（Derrick Henry Lehmer）隨後於1930年代將其改進。

網際網路梅森質數大搜索用這個檢驗法找到了不少很大的質數，最近幾個最大的質數就是這個項目發現的。由於梅森數比隨機選擇的整數更有可能是質數，因此他們認為這是一個極有用的方法。

## 方法

盧卡斯－萊默檢驗法原理是這樣：

令梅森數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, ...

那麼Mp是素數若且唯若

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

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

## 正確性的證明

我們注意到${\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 \\ <pre> & = & \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.布魯斯給出。

假設$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$。但由於q是$M_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是模 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}) \\ <pre> & = & 6 + 2(3^{(M_p-1)/2})\sqrt{3} \\ & = & 6 + 2(-1)\sqrt{3} \\ & = & 6 - \sigma. </pre> \end{array}$$

簡單計算可知 $\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} \\ <pre> & = & (6 + \sigma)^{M_p}(6 + \sigma)/(24 \times 24^{(M_p-1)/2}) \\ & = & (6 - \sigma)(6 + \sigma)/(-24) \\ & = & -1. </pre> \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。

## 外部連結

- GIMPS (The Great Internet Mersenne Prime Search)
- A proof of Lucas–Lehmer–Reix test (for Fermat numbers)
- Lucas–Lehmer test at MersenneWiki