亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

方法

盧卡斯－萊默檢驗(yàn)法原理是這樣：令梅森數(shù) Mp = 2? 1作為檢驗(yàn)對(duì)象（預(yù)設(shè)p是素?cái)?shù)，否則Mp就是合數(shù)了）。定義序列{si }：所有的i ≥ 0

這個(gè)序列的開始幾項(xiàng)是4,14,194, 37634, ... （OEIS中的數(shù)列A003010） 那么Mp是素?cái)?shù)當(dāng)且僅當(dāng)

否則, Mp是合數(shù)。sp ? 2模Mp的余數(shù)叫做p的盧卡斯－萊默余數(shù)。

例子

假設(shè)我們想驗(yàn)證M3 = 7是素?cái)?shù)。我們從s=4開始，并更新3?2 = 1次，把所有的得數(shù)模7：

s ← ((4×4) ? 2) mod 7 = 0

由于我們最終得到了一個(gè)能被7整除的s，因此M3是素?cái)?shù)。

另一方面，M11 = 2047 = 23×89就不是素?cái)?shù)。我們?nèi)匀粡膕=4開始，并更新11?2 = 9次，把所有的得數(shù)模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不是素?cái)?shù)。但是，我們從這個(gè)檢驗(yàn)法仍然無法知道2047的因子，只知道它的盧卡斯-萊默余數(shù)1736。

正確性的證明

我們注意到? ? -->si? ? -->{\displaystyle {\langle }s_{i}{\rangle }}是一個(gè)具有閉式解的遞推關(guān)系。定義ω ω -->=2+3{\displaystyle \omega =2+{\sqrt {3}}}及ω ω -->ˉ ˉ -->=2? ? -->3{\displaystyle {\bar {\omega }}=2-數(shù)學(xué)歸納法t {3}}}；我們可以用數(shù)學(xué)歸納法來驗(yàn)證對(duì)于所有i，都有si=ω ω -->2i+ω ω -->ˉ ˉ -->2i{\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}：

最后一個(gè)步驟可從ω ω -->ω ω -->ˉ ˉ -->=(2+3)(2? ? -->3)=1{\displaystyle \omega {\bar {\omega }}=(2+{\sqrt {3}})(2-{\sqrt {3}})=1}推出。在兩個(gè)部分中，我們都將用到這個(gè)結(jié)果。

充分性

我們希望證明sp? ? -->2≡ ≡ -->0(modMp){\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}意味著Mp{\displaystyle M_{p}}是素?cái)?shù)。我們敘述一個(gè)利用初等群論的證明，布魯斯 W.布魯斯給出。

假設(shè)sp? ? -->2≡ ≡ -->0(modMp){\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}。那么對(duì)于某個(gè)整數(shù)k，有ω ω -->2p? ? -->2+ω ω -->ˉ ˉ -->2p? ? -->2=kMp{\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}}，以及：

現(xiàn)在假設(shè)Mp是合數(shù)，其非平凡素因子q > 2（所有梅森素?cái)?shù)都是奇數(shù)）。定義含有q個(gè)元素的集合X={a+b3|a,b∈ ∈ -->Zq}{\displaystyle X=\{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{q}\}}，其中Zq{\displaystyle \mathbb {Z} _{q}}是模q的有限域是一個(gè)有限域。X中的乘法運(yùn)算定義為：

由于q > 2，因此ω ω -->{\displaystyle \omega }和ω ω -->ˉ ˉ -->{\displaystyle {\bar {\omega }}}位于X內(nèi)。任何兩個(gè)位于X內(nèi)的數(shù)的乘積也一定位于X內(nèi)，但它不是一個(gè)群，因?yàn)椴皇撬械脑豿都有逆元素y，使得xy = 1。如果我們只考慮有逆元素的元素，我們便得到了一個(gè)群X*，它的大小最多為q2? ? -->1{\displaystyle q^{2}-1}（因?yàn)?沒有逆元素）。

現(xiàn)在，由于Mp≡ ≡ -->0(modq){\displaystyle M_{p}\equiv 0{\pmod {q}}}，且ω ω -->∈ ∈ -->X{\displaystyle \omega \in X}，我們有kMpω ω -->2p? ? -->2=0{\displaystyle kM_{p}\omega ^{2^{p-2}}=0}，根據(jù)方程(1)可得ω ω -->2p? ? -->1=? ? -->1{\displaystyle \omega ^{2^{p-1}}=-1}。兩邊平方，得ω ω -->2p=1{\displaystyle \omega ^{2^{p}}=1}，證明了ω ω -->{\displaystyle \omega }是可逆的，其逆元素為ω ω -->2p? ? -->1{\displaystyle \omega ^{2^{p}-1}}，因此位于X*內(nèi)，它的目能整除2p{\displaystyle 2^{p}}。實(shí)際上，這個(gè)階必須等于2p{\displaystyle 2^{p}}，因?yàn)棣?ω -->2p? ? -->1≠ ≠ -->1{\displaystyle \omega ^{2^{p-1}}\neq 1}，因此這個(gè)階不能整除2p? ? -->1{\displaystyle 2^{p-1}}。由于群元素的階最多就是群的大小，我們便得出結(jié)論，2p≤ ≤ -->q2? ? -->1Mp=2p? ? -->1{\displaystyle q^{2}\leq M_{p}=2^{p}-1}，得出矛盾2p1{\displaystyle 2^{p}<2^{p}-1}。因此Mp{\displaystyle M_{p}}是素?cái)?shù)。

必要性

我們假設(shè)Mp{\displaystyle M_{p}}是素?cái)?shù)，欲推出sp? ? -->2≡ ≡ -->0(modMp){\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}。我們敘述一個(gè)?ystein J. R. ?dseth的證明。首先，注意到3是模 Mp的二次非剩余，這是因?yàn)閷?duì)于奇數(shù)p > 1，2 ? 1只取得值7 m勒讓德符號(hào)，因此從勒讓德符號(hào)的性質(zhì)可知(3|Mp){\displaystyle (3|M_{p歐拉}是?1。根據(jù)歐拉準(zhǔn)則，可得：

另一方面，2是模Mp{\displaystyle M_{p}}的二次剩余，這是因?yàn)?p≡ ≡ -->1(modMp){\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}，因此2≡ ≡ -->2p+1=(2(p+1)/2)2(modMp){\displaystyle 2\equiv 2^{p+1}=\left(2^{(p+1)/2}\right)^{2}{\pmod {M_{p}}}}。根據(jù)歐拉準(zhǔn)則，可得：

接著，定義σ σ -->=23{\displaystyle \sigma =2{\sqrt {3}}}，并像前面那樣，定義X*為{a+b3|a,b∈ ∈ -->ZMp}{\displaystyle \{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{M_{p}}\}}的乘法群。我們引理到以下的引理：

（根據(jù)費(fèi)馬小定理），以及

對(duì)于所有整數(shù)a（費(fèi)馬小定理）。

那么，在群X*中，我們有：

簡(jiǎn)單計(jì)算可知 ω ω -->=(6+σ σ -->)2/24{\displaystyle \omega =(6+\sigma )^{2}/24}。我們可以用這個(gè)結(jié)果來計(jì)算群X*中的ω ω -->(Mp+1)/2{\displaystyle \omega ^{(M_{p}+1)/2}}：

其中我們用到了以下的事實(shí)：

由于Mp≡ ≡ -->3(mod4){\displaystyle M_{p}\equiv 3{\pmod {4}}}，我們還需要做的就是把方程的兩邊乘以ω ω -->ˉ ˉ -->(Mp+1)/4{\displaystyle {\bar {\omega }}^{(M_{p}+1)/4}}，并利用ω ω -->ω ω -->ˉ ˉ -->=1{\displaystyle \omega {\bar {\omega }}=1}：

由于sp?2是整數(shù)，且在X*內(nèi)是零，因此它也是零mod Mp。

參見

梅森素?cái)?shù)

因特網(wǎng)梅森素?cái)?shù)大搜索（GIMPS）

新梅森猜想

埃拉托斯特尼篩法

米勒-拉賓檢驗(yàn)

試除法

費(fèi)馬素性檢驗(yàn)

參考文獻(xiàn)

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

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請(qǐng)告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。