基于遞歸性質(zhì)的偽梅森素數(shù)的生成方法*

張艷碩 周岐浩 劉 冰 滕樹晨

北京電子科技學(xué)院，北京市 100070

1 引言

梅森素數(shù)[1]是數(shù)論研究中的一項重要內(nèi)容，自古希臘時代起人們就開始了對梅森素數(shù)的探索。由于這種素數(shù)具有獨特的性質(zhì)，一直吸引著歐幾里得、費爾馬、歐拉等眾多數(shù)學(xué)家和無數(shù)的數(shù)學(xué)愛好者對它進行探究。在現(xiàn)代，梅森素數(shù)在計算機科學(xué)、密碼學(xué)等領(lǐng)域也有重要的應(yīng)用價值。20世紀(jì)90年代中后期，建立了世界上第一個基于互聯(lián)網(wǎng)的分布式計算項目——因特網(wǎng)梅森素數(shù)大搜索[3](GIMPS)。2017年12月26日發(fā)現(xiàn)了第50個梅森素數(shù)，超大素數(shù)有23249425位數(shù)，再次刷新了已知最大素數(shù)紀(jì)錄。

偽梅森數(shù)是最近提出的根據(jù)梅森數(shù)變形的具有(2P-c)形式的一類數(shù)，其中p為素數(shù)，c為小奇數(shù)，并用M(p，c)表示。當(dāng)c＝1時，偽梅森數(shù)即為梅森數(shù)。另外，當(dāng)一個數(shù)既是偽梅森數(shù)又是素數(shù)時，將其稱為偽梅森素數(shù)[7]。

偽梅森數(shù)的提出大大地拓寬了大素數(shù)的產(chǎn)生渠道。發(fā)現(xiàn)偽梅森素數(shù)需要素數(shù)判別和數(shù)值計算的理論與方法以及高超巧妙的程序設(shè)計技術(shù)。它促進了分布式計算技術(shù)的發(fā)展，在推動計算機功能改進方面發(fā)揮了獨特作用。偽梅森素數(shù)的研究推動了數(shù)論的發(fā)展，促進了計算數(shù)學(xué)和程序設(shè)計技術(shù)的發(fā)展[5]。

本文根據(jù)偽梅森數(shù)的定義推出一些相關(guān)性質(zhì)并提出基于遞歸性質(zhì)的偽梅森數(shù)的生成方法以及偽梅森數(shù)在構(gòu)造RSA[6]密鑰、ElGamal[2]密鑰和Diffie-Hellman[4]密鑰協(xié)商上的應(yīng)用。

2 偽梅森數(shù)

本文先從梅森數(shù)的定義[1]列出有關(guān)偽梅森數(shù)的兩個定義。

定義1將形如2p-c形式的正整數(shù)用M(p，c) 表示，其中p為素數(shù)，c為3、5、7 等小奇數(shù)，稱為偽梅森數(shù)。當(dāng)M(p，c)為素數(shù)時，我們將其稱為偽梅森素數(shù)

如：M(3，3)＝ 5 為偽梅森素數(shù)，而M(5，5)＝27為偽梅森數(shù)而非偽梅森素數(shù)。

注：針對定義1特殊說明整數(shù)2為唯一的偶素數(shù)，表示為M(2，2)，這個是c唯一為偶數(shù)的情況。本文對M(2，2)作為特殊情況另行討論。當(dāng)c＝1時，偽梅森數(shù)退化為梅森數(shù)。

定義2約束定義：若整數(shù) k同時滿足M(p1，c1)和M(p2，c2)，且p1＜p2，即

那么將k定義為偽梅森數(shù)M(p1，c1)而非M(p2，c2)。

如：3＝M(2，1)＝M(3，5)，根據(jù)定義2，將3定義為M(2，1) 而非M(3，5)。

這里規(guī)定了整數(shù)k的最簡定義，避免了重復(fù)定義造成的資源浪費。

3 偽梅森素數(shù)的性質(zhì)

本文從偽梅森數(shù)與梅森數(shù)關(guān)系以及偽梅森數(shù)之間的遞歸關(guān)系，推出了偽梅森數(shù)的7個性質(zhì)。

性質(zhì)1對于任意素數(shù)p，奇數(shù)c1，c2，c3有

證明：

性質(zhì)2對于任意素數(shù)p，奇數(shù) c，有M(p，c)與c互素。

證明：

性質(zhì)3對于任意素數(shù)p，奇數(shù)c，若滿足2N-1＜c＜2N，則對于偽梅森數(shù)M(p，c)有：

證明：

假設(shè)

利用該定理可以利用兩個小梅森數(shù)構(gòu)造大的偽梅森數(shù)。

推論1：當(dāng)N是偶數(shù)且c≡1mod6時，和均為整數(shù)，或當(dāng) N是奇數(shù)且 c≡5mod6、時，均為整數(shù)。

證明：

①若N是偶數(shù)，則2N-1≡0mod3

偽梅森數(shù)的定義中c為奇數(shù)，則

所以：

②若N是奇數(shù)，則2N-1≡1mod3。

偽梅森數(shù)的定義中c為奇數(shù)，則

所以：

性質(zhì)4對于任意素數(shù)p1，p2，小奇數(shù)c1，且p1≥p2，有

性質(zhì) 5對于任意素數(shù)p1，p2，奇數(shù)c1，c2，且p1≥p2，有

證明：

性質(zhì)6對于任意素數(shù)p1，p2，小奇數(shù)c1，c2，且p1≥p2，有

證明：

特別的，當(dāng)c1＝c2＝c時，上式變?yōu)?/p>

注：根據(jù)上述等式判斷M(p1，c)與偽梅森素數(shù)M(p2，c)的互素情況，當(dāng)?shù)仁接疫厼榉?整數(shù)時，M(p1，c)與M(p2，c)不互素，否則二者互素。由于2p1-p2為整數(shù)，只需判斷的整數(shù)性。

由性質(zhì)2可知M(p2，c)與c互素，故當(dāng)2M(p1-p2-1，1)＋1與M(p2，c)互素時M(p1，c)與M(p2，c) 互素。由此我們得到性質(zhì)7：

性質(zhì)7對于任意素數(shù)p1，p2，小奇數(shù)c，且p1≥p2，M(p1，c)與偽梅森素數(shù)M(p2，c) 互素的充分必要條件為 2M(p1-p2-1，1)＋1與M(p2，c) 互素。

例1若p1＝7，p2＝3，c＝3，即M(7，3)＝125與M(3，3)＝5，易知二者不互素。p1-p2-1＝3，那么2M(3，1)＋1＝15與M(3，3)＝5也不互素。

若p1＝11，p2＝5，c＝3，即M(11，3)＝2045與M(5，3)＝29，易知二者互素。p1-p2-1＝5，那么2M(5，1)＋1＝63與M(5，3)＝29也互素。

4 偽梅森素數(shù)的產(chǎn)生方法

接下來本文將利用等式(1)得到新的偽梅森數(shù)的生成方法。在等式(1)中，有：

對于任意素數(shù)p1，p2，奇數(shù)c，有

說明：利用等式(1)我們可以通過兩個低次的梅森數(shù)和一個低次的偽梅森數(shù)生成高次偽梅森數(shù)。

由于梅森數(shù)已有公開的數(shù)表，在使用梅森數(shù)時可以直接套用數(shù)表上的數(shù)進行計算。梅森素數(shù)表列舉如表1所示(以偽梅森素數(shù)形式表示)：

表1 前12個梅森素數(shù)[1]

表2 第13至50號梅森素數(shù) [1]

從遞歸性質(zhì)出發(fā)，根據(jù)上述定義可以不斷推出新的偽梅森數(shù)這個思想在生成素數(shù)上具有廣泛應(yīng)用，具體步驟如下：

步驟1固定c＝t不變，依次選擇素數(shù)p1，p2，其中p1，p2為存在于梅森素數(shù)表中，且M(p1，c) 為素數(shù)。

步驟2利用等式(1)生成新的偽梅森數(shù)。

步驟3對新的偽梅森素數(shù)進行素性檢驗(包括是 Miller-Rabin檢驗[9]，Lucas-Lehmer檢驗[8]等(注：Lucas-Lehmer是針對梅森素數(shù)的素性檢驗，當(dāng)拓展為偽梅森素數(shù)時，該檢驗并不能通過))，通過則將新偽梅森素數(shù)加入偽梅森素數(shù)表(c＝t)，并回到步驟1。若不通過檢驗，則拋棄該數(shù)，回到步驟1，重新選擇p1，p2。

這樣便得到一個新的偽梅森素數(shù)表族(c＝t)。

我們以偽梅森素數(shù)舉例說明：

5 性能分析

5.1 復(fù)雜度

通過直接生成一個新的偽梅森素數(shù)M(p，c)，需要消耗時間復(fù)雜度O(2p)，而消耗的空間復(fù)雜度為O(1)。 時空分配不合理，當(dāng)p值較大時很容易造成溢出。

根據(jù)遞歸方法生成素數(shù)方法，通過建立數(shù)表來增加空間復(fù)雜度為O(n2)，但時間復(fù)雜度降低為O(22p1)，其中2p1＝p-p2。增加了時空分配的合理性，大大提高了性能。

5.2 效率

使用遞歸性質(zhì)尋找偽梅森素數(shù)效率比使用普通方法效率提高很多。其中包括執(zhí)行的時間，執(zhí)行時間需通過依據(jù)編制的程序在計算機上運行時所消耗的時間來度量。由于復(fù)雜度的降低，在計算機上的執(zhí)行時間也大幅降低。

6 應(yīng)用

6.1 基于偽梅森素數(shù)的RSA密鑰對的生成

RSA[6]是第一個安全，實用的公鑰密碼算法，成為了公鑰密碼的國際標(biāo)準(zhǔn)，目前是應(yīng)用最廣泛的公鑰密碼體制。RSA密碼算法的數(shù)學(xué)原理來源于歐拉定理，其安全性取決于大整數(shù)因子分解不易實現(xiàn)。公鑰密碼體制在加密和數(shù)字簽名上應(yīng)用廣泛，不僅安全、易懂，還容易實現(xiàn)。

RSA密鑰對的生成，通常需要以下幾個步驟：

(1)選取兩個大素數(shù)p、q；

(2)計算乘積n＝p×q，φ(n)＝(p-1)×(q-1)，其中φ(n)是n的歐拉函數(shù)值；

(3)隨機數(shù)e(1＜e＜φ(n))(不用保密)，必須滿足e與φ(n)互素；

(4)通過擴展歐幾里得算法計算d，滿足d×e≡1modφ(n)(保密)，即d-1≡emodφ(n) ；通常把 (e，n)稱為公鑰，(d，φ(n))稱為私鑰，e和d分別稱為加密指數(shù)和解密指數(shù)，在不知道p和q的情況下，很難計算φ(n)，因而就不知道私鑰(d，φ(n))。

例4：我們利用在例2和例3生成的偽梅森素數(shù)運算說明。

設(shè)p＝M(17，9)＝131063，q＝M(29，3)＝536870909，求 d。

選擇公鑰 e＝13(素數(shù))，求出d＝924900521。

所以，得到公鑰(e，n)＝(13，70363911946267)，私鑰為(d，φ(n))＝(924900521，70363374944296)。

由于梅森素數(shù)具有2p-1的形式，故容易受到William’sp＋1[10]因式分解攻擊。而偽梅森素數(shù)以2p-c形式作為因子，從而避免受到William攻擊。

6.2 基于偽梅森素數(shù)的EIGamal密鑰對生成

ElGamal[2]算法，是一種較為常見的加密算法，它是基于1985年提出的公鑰密碼體制和橢圓曲線加密體系。既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計算有限域上離散對數(shù)這一難題。在加密過程中，生成的密文長度是明文的兩倍，且每次加密后都會在密文中生成一個隨機數(shù)K，在密碼中主要應(yīng)用離散對數(shù)問題的幾個性質(zhì)：求解離散對數(shù)(可能)是困難的，而其逆運算指數(shù)運算可以應(yīng)用平方-乘的方法有效地計算。也就是說，在適當(dāng)?shù)娜篏中，指數(shù)函數(shù)是單向函數(shù)。

密鑰對產(chǎn)生辦法如下：首先選擇一個素數(shù)p，獲取一個素數(shù)p的一個原根g(若g模p的階等于φ(p)，則稱g為模p的一個原根。(其中φ(p)表示p的歐拉函數(shù)，即所有小于等于p的正整數(shù)中和p互質(zhì)的整數(shù)的個數(shù)))和一個隨機數(shù)x，且g和x均小于p，計算y＝gx(modp)，則其公鑰為y，g和p，私鑰是x可由一組用戶共享。

ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個隨機數(shù)k，k與p-1互質(zhì)，計算

再用擴展 Euclidean算法對下面方程求解b：

簽名就是(a，b)。隨機數(shù)k須丟棄。

驗證時要驗證下式：

得到公鑰(y，g，p)＝(410263748，3，536870909)，私鑰為(x)＝(131063)。

6.3 基于偽梅森素數(shù)的ECC密鑰對生成

橢圓曲線密碼學(xué)(英語：Elliptic curve cryptography，縮寫為ECC)，一種建立公開密鑰加密的演算法，基于橢圓曲線數(shù)學(xué)。橢圓曲線在密碼學(xué)中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。

ECC的主要優(yōu)勢是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密算法——提供相當(dāng)?shù)幕蚋叩燃壍陌踩CC的另一個優(yōu)勢是可以定義群之間的雙線性映射，基于Weil對或是Tate對；雙線性映射已經(jīng)在密碼學(xué)中發(fā)現(xiàn)了大量的應(yīng)用，例如基于身份的加密。

同時一定要檢驗是否滿足1≤a＜p。否則簽名容易偽造。

ElGamal用于加密。被加密信息為M，首先選擇一個隨機數(shù)k，k與p-1互質(zhì)，計算

(a，b)為密文，是明文的兩倍長。解密時計算

ElGamal簽名的安全性依賴于乘法群上的離散對數(shù)計算。素數(shù)p必須足夠大，且p-1至少包含一個大素數(shù)。

因子以抵抗Pohlig＆Hellman算法的攻擊。M一般都應(yīng)采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴于p和g，若選取不當(dāng)則簽名容易偽造，應(yīng)保證g對于p-1的大素數(shù)因子不可約。

例5：設(shè)p＝M(29，3)＝536870909，g＝3是p的一個原根，選擇隨機數(shù)x＝M(17，9)＝131063。不過一個缺點是加密和解密操作的實現(xiàn)比其他機制花費的時間長。

ECC的密鑰對產(chǎn)生方法如下：

定義在Fp上的橢圓曲線：

橢圓曲線E(Fp)定義為：

其中O是無窮遠(yuǎn)點。橢圓曲線E(Fp)上的點數(shù)目用＃E(Fp)表示，稱為橢圓曲線E(Fp)的階。

設(shè)橢圓曲線參數(shù)(p，a，b，G，n)，其中G是基點，n是G的階。在區(qū)間[1，n-1]中隨機選取一個整數(shù)dB為私鑰。計算點QB＝dBG，取點QB為公鑰。

加密過程：

(1)用戶A將待傳輸?shù)拿魑木幋a到Ep(a，b)上一點M，并產(chǎn)生一個隨機整數(shù)r。

(2)用戶A計算點C1＝M＋rQB；C2＝kG。

(3)用戶A將C1、C2傳給用戶B。

(4)用戶B接到信息后，計算C1-kC2-kC2，結(jié)果就是點M，再對點M進行解碼就可以得到明文。

例6：設(shè)p＝M(5，9)＝23，a＝1，b＝1，G＝(3，10)，n＝28

隨機數(shù)作為私鑰dB＝M(17，9)＝9

公鑰QB＝(4，21)

6.4 基于偽梅森素數(shù)的密鑰交換協(xié)議

Diffie-Hellman[4]密鑰交換協(xié)議，縮寫為D-H，是一種安全協(xié)議。它可以讓雙方在完全沒有對方任何預(yù)先信息的條件下通過不安全信道創(chuàng)建起一個密鑰。這個密鑰可以在后續(xù)的通訊中作為對稱密鑰來加密通訊內(nèi)容。

例8：首先確定p＝M(29，3)＝536870909，g＝3是p的一個原根。

(1)Alice選擇不公開的整數(shù)a＝M(17，9)＝131063，然后傳送給 BobA＝gamodp，即A＝3131063mod536870909＝410263748；

(2)Bob同樣選擇一個不公開整數(shù)b＝17，然后傳送給 AliceB＝gbmodp，即B≡317mod536870909≡387420489；

(3)Alice計算s＝Bamodp，即s＝387420489131063mod536870909＝48621887；

(4)Bob計算s＝Abmodp，即s＝41026374817mod536870909＝48621887；

Alice和Bob就能通過公開信道得到密鑰s＝48621887。

7 結(jié)論

隨著現(xiàn)代密碼學(xué)的不斷發(fā)展，素數(shù)在信息安全領(lǐng)域以及密碼保密領(lǐng)域起到了越來越大的作用，計算機計算能力不斷增強，許多依賴于計算量的問題迎刃而解，對于大素數(shù)的要求會更高，而偽梅森數(shù)是最近所提出的一類拓寬大素數(shù)生成的渠道。本文對偽梅森素數(shù)進行前瞻性的研究，根據(jù)偽梅森素數(shù)的定義提出一些相關(guān)性質(zhì)，并根據(jù)性質(zhì)得出遞歸方法的偽梅森數(shù)的生成方法，再基于該性質(zhì)形成了一系列偽梅森素數(shù)族。

對于檢驗梅森素數(shù)的Lucas-Lehmer檢驗，并不能直接應(yīng)用于偽梅森素數(shù)。我們希望讀者在閱讀本文后得到啟發(fā)，推出類似素性檢驗方法以檢驗偽梅森素數(shù)。