數學中,盧卡斯-萊默質數判定法(英語:Lucas–Lehmer primality test)是檢驗梅森數的質性檢驗,是由愛德華·盧卡斯於1878年完善,德里克·亨利·萊默隨後於1930年代將其改進。
互聯網梅森質數大搜索用這個檢驗法找到了不少很大的質數,最近幾個最大的質數就是這個項目發現的。[1]由於梅森數比隨機選擇的整數更有可能是質數,因此他們認為這是一個極有用的方法。
盧卡斯-萊默檢驗法原理是這樣:
令梅森數
Mp = 2p− 1作為檢驗物件(預設p是質數,否則Mp就是合數了)。
定義序列{si }:所有的i ≥ 0
|
,如果 ;
|
,如果 。
|
- .
- .
- .
這個序列的開始幾項是4, 14, 194, 37634, ... (OEIS數列A003010)
那麼Mp是質數當且僅當
![{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/927bf8c53e8606aee46b2aa67843462e2dc0dfce)
否則, 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。
正確性的證明[編輯]
我們注意到
是一個具有閉式解的遞歸關係。定義
及
;我們可以用數學歸納法來驗證對於所有i,都有
:
。
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/326a6e6398dffcc03228d560068101f83680e12c)
最後一個步驟可從
推出。在兩個部分中,我們都將用到這個結果。
充分性[編輯]
我們希望證明
意味着
是質數。我們敘述一個利用初等群論的證明,由J. W.布魯斯給出[2]。
假設
。那麼對於某個整數k,有
,以及:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fd3fd20a6f31a5ef5dfc1f173e1abcfeba52c18)
現在假設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*為
的乘法群。我們將用到以下的引理:
![{\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/201dfd84053e5e181725159e9c9dc472c27668a6)
(根據費馬小定理),以及
![{\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bf4c4d54cefab92adb2e98a7489f76529e99729)
對於所有整數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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2f4bb5cc6bfa06eec09e64a303ddd3cde0459e)
簡單計算可知
。我們可以用這個結果來計算群X*中的
:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a6f18bf219de984b98bf12269fe3f6d713b185d)
其中我們用到了以下的事實:
。
由於
,我們還需要做的就是把方程的兩邊乘以
,並利用
:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82616dbe232d8dce78037b823f02f80851a81b04)
由於sp−2是整數,且在X*內是零,因此它也是零mod Mp。
- ^ GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what (頁面存檔備份,存於互聯網檔案館)
- ^ 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.
- ^ Ö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 (頁面存檔備份,存於互聯網檔案館)
參考文獻[編輯]
外部連結[編輯]