盧卡斯-萊默質數判定法

盧卡斯-萊默質數判定法(英語:Lucas–Lehmer primality test),是數學中檢驗梅森數質性檢驗,由法國數學家愛德華·盧卡斯Édouard Lucas)於1878年完善,美國數學家德里克·亨利·萊默Derrick Henry Lehmer)隨後於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頁面存檔備份,存於互聯網檔案館

參考文獻

外部連結