盧卡斯-萊默質數判定法

數學中，**盧卡斯 - 萊默質數判定法**（英語：Lucas–Lehmer primality test）是檢定梅森數的質性檢定，是由愛德華・盧卡斯於 1878 年完善，德里克・亨利・萊默隨後於 1930 年代將其改進。

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

## 方法

盧卡斯－萊默檢定法原理是這樣： 
令梅森數 _M_p = 2p− 1 作為檢定物件（預設 _p_ 是質數，否則 _M_p 就是合數了）。 

定義序列 {_s_i }：所有的 _i_ ≥ 0 

　
: :

　
: .

　
: .

　
: .

這個序列的開始幾項是 4, 14, 194, 37634, ... （OEIS 數列 A003010） 

那麼 _M_p 是質數若且唯若 

　
: $s_{p-2}\equiv 0{\pmod {M_{p}}};$

否則， _M_p 是合數。 
_s_p − 2 模 _M_p 的餘數叫做 _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}\equiv 0{\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}}$

現在假設 _M_p 是合數，其非平凡質因子 _q_> 2（所有梅森質數都是奇數）。定義含有 _q_2 個元素的集合 $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}\equiv 0{\pmod {M_{p}}}$ 。我們敘述一個 Öystein J. R.
Ödseth 的證明。首先，注意到 3 是模 _M_p 的二次非剩餘，這是因為對於奇數 _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}}$

簡單計算可知 $\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}}$

由於 _s_p−2 是整數，且在 _X_\* 內是零，因此它也是零 mod_M_p。

## 參見

* 梅森質數
* 網際網路梅森質數大搜索（GIMPS）
* 新梅森猜想
* 埃拉托斯特尼篩法
* 米勒 - 拉賓檢定
* 試除法
* 費馬質性檢定
* 盧卡斯 - 萊默質數判定法
* 孿生質數
* 三胞胎質數
* 四胞胎質數
* 質數判定法則
* 表兄弟質數
* 六質數
* X²+1 質數

## 注釋

## 參考文獻

* Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective 1st edition. Springer. 2001. ISBN 978-0-387-94777-8.  引文格式 1 維護：冗餘文本 (link) Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

## 外部連結

* 埃里克・韋斯坦因。卢卡斯 - 莱默检验法. MathWorld.
* GIMPS (The Great Internet Mersenne Prime Search)（頁面存檔備份，存於網際網路檔案館）
* A proof of Lucas–Lehmer–Reix test (for Fermat numbers) （頁面存檔備份，存於網際網路檔案館）
* Lucas–Lehmer test at MersenneWiki