盧卡斯-萊默質數判定法

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

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

方法

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

定義序列{s_i }：所有的i ≥ 0

${\displaystyle s_{i}={\begin{cases}\;\;\,4\\s_{i-1}^{2}-2\end{cases}}}$	，如果${\displaystyle \displaystyle i=0}$；
	，如果${\displaystyle \displaystyle i>0}$。

.

.

.

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

那麼M_p是質數當且僅當

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

否則, M_p是合數。
s_{p − 2}模M_p的餘數叫做p的盧卡斯－萊默餘數。

例子

假設我們想驗證M₃ = 7是質數。我們從s=4開始，並更新3−2 = 1次，把所有的得數模7：

• s ← ((4×4) − 2) mod 7 = 0

由於我們最終得到了一個能被7整除的s，因此M₃是質數。

另一方面，M₁₁ = 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整除，因此M₁₁=2047不是質數。但是，我們從這個檢驗法仍然無法知道2047的因子，只知道它的盧卡斯-萊默餘數1736。

正確性的證明

我們注意到${\displaystyle {\langle }s_{i}{\rangle }}$是一個具有閉式解的遞歸關係。定義${\displaystyle \omega =2+{\sqrt {3}}}$及${\displaystyle {\bar {\omega }}=2-{\sqrt {3}}}$；我們可以用數學歸納法來驗證對於所有i，都有${\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}$：

${\displaystyle s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=(2+{\sqrt {3}})+(2-{\sqrt {3}})=4}$。

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

最後一個步驟可從${\displaystyle \omega {\bar {\omega }}=(2+{\sqrt {3}})(2-{\sqrt {3}})=1}$推出。在兩個部分中，我們都將用到這個結果。

充分性

我們希望證明${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$意味着${\displaystyle M_{p}}$是質數。我們敘述一個利用初等群論的證明，由J. W.布魯斯給出^[2]。

假設${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$。那麼對於某個整數k，有${\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}}$，以及：

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

現在假設M_p是合數，其非平凡質因子q > 2（所有梅森質數都是奇數）。定義含有q²個元素的集合${\displaystyle X=\{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{q}\}}$，其中${\displaystyle \mathbb {Z} _{q}}$是模q的整數，是一個有限體。X中的乘法運算定義為：

${\displaystyle (a+b{\sqrt {3}})(c+d{\sqrt {3}})=[(ac+3bd){\hbox{ mod }}q]+[(bc+ad){\hbox{ mod }}q]{\sqrt {3}}}$.

由於q > 2，因此${\displaystyle \omega }$和${\displaystyle {\bar {\omega }}}$位於X內。任何兩個位於X內的數的乘積也一定位於X內，但它不是一個群，因為不是所有的元素x都有反元素y，使得xy = 1。如果我們只考慮有反元素的元素，我們便得到了一個群X*，它的大小最多為${\displaystyle q^{2}-1}$（因為0沒有反元素）。

現在，由於${\displaystyle M_{p}\equiv 0{\pmod {q}}}$，且${\displaystyle \omega \in X}$，我們有${\displaystyle kM_{p}\omega ^{2^{p-2}}=0}$，根據方程(1)可得${\displaystyle \omega ^{2^{p-1}}=-1}$。兩邊平方，得${\displaystyle \omega ^{2^{p}}=1}$，證明了${\displaystyle \omega }$是可逆的，其反元素為${\displaystyle \omega ^{2^{p}-1}}$，因此位於X*內，它的目能整除${\displaystyle 2^{p}}$。實際上，這個階必須等於${\displaystyle 2^{p}}$，因為${\displaystyle \omega ^{2^{p-1}}\neq 1}$，因此這個階不能整除${\displaystyle 2^{p-1}}$。由於群元素的階最多就是群的大小，我們便得出結論，${\displaystyle 2^{p}\leq q^{2}-1<q^{2}}$。但由於q是${\displaystyle M_{p}}$的一個非平凡質因子，我們必須有${\displaystyle q^{2}\leq M_{p}=2^{p}-1}$，得出矛盾${\displaystyle 2^{p}<2^{p}-1}$。因此${\displaystyle M_{p}}$是質數。

必要性

我們假設${\displaystyle M_{p}}$是質數，欲推出${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$。我們敘述一個Öystein J. R. Ödseth的證明^[3]。首先，注意到3是模 M_p的二次非剩餘，這是因為對於奇數p > 1，2 ^p − 1隻取得值7 mod 12，因此從勒壤得符號的性質可知${\displaystyle (3|M_{p})}$是−1。根據歐拉準則，可得：

${\displaystyle 3^{(M_{p}-1)/2}\equiv -1{\pmod {M_{p}}}}$.

另一方面，2是模${\displaystyle M_{p}}$的二次剩餘，這是因為${\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}$，因此${\displaystyle 2\equiv 2^{p+1}=\left(2^{(p+1)/2}\right)^{2}{\pmod {M_{p}}}}$。根據歐拉準則，可得：

${\displaystyle 2^{(M_{p}-1)/2}\equiv 1{\pmod {M_{p}}}}$.

接着，定義${\displaystyle \sigma =2{\sqrt {3}}}$，並像前面那樣，定義X*為${\displaystyle \{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{M_{p}}\}}$的乘法群。我們將用到以下的引理：

${\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}$

（根據費馬小定理），以及

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$

對於所有整數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}}}$

簡單計算可知 ${\displaystyle \omega =(6+\sigma )^{2}/24}$。我們可以用這個結果來計算群X*中的${\displaystyle \omega ^{(M_{p}+1)/2}}$：

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

其中我們用到了以下的事實：

${\displaystyle 24^{(M_{p}-1)/2}=(2^{(M_{p}-1)/2})^{3}(3^{(M_{p}-1)/2})=(1)^{3}(-1)=-1}$。

由於${\displaystyle M_{p}\equiv 3{\pmod {4}}}$，我們還需要做的就是把方程的兩邊乘以${\displaystyle {\bar {\omega }}^{(M_{p}+1)/4}}$，並利用${\displaystyle \omega {\bar {\omega }}=1}$：

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

由於s_p−2是整數，且在X*內是零，因此它也是零mod M_p。

參見

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

註釋

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. 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