用數(shù)域篩法分解大整數(shù)

本文格式為Word版，下載可任意編輯——用數(shù)域篩法分解大整數(shù)

用數(shù)域篩法分解大整數(shù)

黃敬騰

（北京師范大學(xué)珠海分校信息技術(shù)與軟件工程學(xué)院0401010050）

摘要:數(shù)域篩法是目前最快的(漸進意義下)整數(shù)分解方法。多項式選擇則是該算法中的一個重要環(huán)節(jié),它關(guān)系到整個算法的運算速度及所耗時間。而影響多項式選擇的兩大因素———大小和根的屬性,是多項式選擇的關(guān)鍵。本文對數(shù)域篩法中多項式大小進行了深入的分析,并通過嚴密的計算給出了不可憐況下,多項式次數(shù)的取值范圍。關(guān)鍵詞:整數(shù)分解;數(shù)域篩法;多項式的大小

PolynomialSelectionintheNumber

FieldSieve

JingtengHuang

(InformationScienceTechnologyBeijingnormaluniversityZhuhaicampus0401010050)Abstract:Thenumberfieldsieve(NFS)istheasymptoticallyfastestmethodknownthusfar.Polynomialselectionisoneimportantpartinthenumberfieldsieve.Itaffectsthespeedandconsumingtimeofthewholealgorithm.Thekeyinthepolynomialselectionisthesizeofthepolynomial.Inthispaper,theauthorsanalysisthesizeofthepolynomialindetail,andpresentawayofchoosingthedegreeofthepolyno2mial.Keywords:factingalgorithm;numberfieldsieve;thesizeofpolynomial

一：引言

眾所周知,早期的公開密鑰RSA系統(tǒng)之所以流行,是由于它是建立在大整數(shù)的分解極其困難的理論基礎(chǔ)之上,因而使RSA系統(tǒng)有很大的安全性。然而,隨著整數(shù)分解算法的不斷改進和計算機運算速度的加快,人們對RSA系統(tǒng)的安全性又產(chǎn)生了懷疑。在二戰(zhàn)期間,英國間諜運用古老的大型計算機成功地破譯了大量的德國軍事情報,為盟軍戰(zhàn)勝法西斯贏的了主動。正是由于計算機的迅猛發(fā)展,加密與解密的對抗和數(shù)論自身理論的提高,整數(shù)分解的研究也就變得特別地活躍,算法不斷地得

到改進。

攻擊RSA加密算法的一種主要手段是大整數(shù)分解。為了校驗當(dāng)前大整數(shù)分解的能力(包括算法和計算機的計算能力),選擇安全的RSA參數(shù),RSA公司從1991年初開始,不斷公布了一系列關(guān)于大整數(shù)分解的挑戰(zhàn)。為此,計算數(shù)論專家發(fā)展了大量大整數(shù)分解算法,例如:p+1方法、p-1方法、Pomerance的二次篩法、Lenstra的橢圓曲線分解方法、Pollard和Pomerance等數(shù)域篩法。其中廣義數(shù)域篩法是目前最有效的算法。RSA挑戰(zhàn)的進展狀況如表1所示。

目前國際上最新的大數(shù)分解理論與技術(shù),包括多項式選取、篩法、過濾、大規(guī)模稀疏線性方程組求解和代數(shù)數(shù)的平方根求解5個步驟。

二：RSA算法簡介

1．RSA算法公鑰，私鑰產(chǎn)生

a)隨機選取的在素數(shù)P和Q，還有N，其中N=P*Q，P和Q保密，N

公開。

b)F(N)=(P-1)*(Q-1)。

c)隨機E，E滿足（2=E=F(N)）,E作為公鑰公開。

d)計算D,使E*D=1(modF(N)),稱D為E對模F(N)的逆，D作為私鑰

保密。

2．RSA算法的加密解密（m為明文，c為密文）Ea)加密算法c=E(m)=m(modN)Db)解密算法m=D(c)=c(modN)

3．RSA算法的特點

a)RSA算法的特點是非對稱加密算法，通過兩個素數(shù)P和Q產(chǎn)生公鑰(E,N)

公開和產(chǎn)生死鑰(D,N)保密。

b)通過公鑰加密的密文只有私鑰可以解密，而通過私鑰加密的密文只有公

鑰可以解迷。加密解密是非對稱的。

c)正是由于RSA算法的特點，因此他可以用于數(shù)字簽字，防欺騙，防抵

賴，在電子商務(wù)領(lǐng)域被廣泛使用。

4．RSA算法的不足。

由于進行的都是大數(shù)計算，使得RSA最快的狀況也比DES慢上100倍，

無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。

三：數(shù)域篩選的思想

一般來說,要把整數(shù)n進行分解尋常是找到兩個整數(shù)x和y,滿足x2≡y2(modn)。然后計算gcd(x-y,n),假使gcd(x-y,n)=1,表示分解失敗,否則就找到了n的兩個真因子。各種篩法所不同的是x,y的找法不一樣。數(shù)域篩法的思想是:

1.構(gòu)造代數(shù)數(shù)域。找一個次數(shù)為d1的首1不可約多項式f和整數(shù)m,使f(m)≡0(modn)。設(shè)A是f的一個根,于是得到擴域K=Q(A),作映射U:Z

[A]—→Z/nZ,由A—→(mmodn)誘導(dǎo)出來。

2．找一個數(shù)對(a,b)的非空集合S,滿足以下條件:

i)對所有(a,b)∈S,gcd(a,b)=1;

ii)Π(a,b)∈S(a+bm)是Z中的平方數(shù);

iii)Π(a,b)∈S(a+bA)是Z[A]中的平方數(shù)。

3.令x∈Z是ii)中數(shù)的平方根,B∈Z[A]是iii)中數(shù)的平方根,令y∈Z適合(ymodn)=U(B),那么我們得到

y2≡x2modn

于是,算出n的因子gcd(x-y,n)。

四：數(shù)域的構(gòu)造

數(shù)域的構(gòu)造實際上是不可約多項式f∈Z[x]的構(gòu)造。在實踐中,對于十進制字1/3節(jié)在110～160之間的數(shù)n,宜取d=5。理論上d=((3

loglogn)1/3,n22d*d1.+o(1))logn/

下面就介紹構(gòu)造f的兩種方法:

方法1假使存在一個比較小的整數(shù)a可以表示為an=re-s的形式,這里r,|s|k*d-e都是比較小的整數(shù),那么可以令k是滿足k*d=e的最小正整數(shù),t=s*r,則得到多項式f=xd-t,取m=rk滿足f(m)≡0modn。

n1/d方法2以“基m的方法找f。取r是一個比較小的正整數(shù),m=[(rn)],然后把rn表示成m進制

R*n=cdmd+cd-1md-1++c0,0=cim

dd2于是得到f=cdx++c0,并且f(m)≡0modn。選取Σi=0ci比較小

的作為我們的f。

四：數(shù)域篩選的多項式時間分析

定義1若一整數(shù)的最大素因子小于或等于B(B為預(yù)先給定的整數(shù)),則稱此整數(shù)為平滑B數(shù)。

令

Fi(x,y)=ydfi(x/y),d=deg(fi)。

在數(shù)域篩法中最關(guān)鍵的問題就是如何建立集合S,我們的方法是通過收集Fi的平滑值從而構(gòu)建集合S:對于某個給定的平滑界B,我們收集互素的整數(shù)對(a,b),使之滿足:F1(a,b)和F2(a,b)為平滑B數(shù)。這時我們稱這樣的整數(shù)對為一個關(guān)系。通過線形代數(shù)的擴張,在這大量的關(guān)系中找出(a,b)∈S,使得

Π(a,b∈S),Fi(a,b)

在Z中為一平方數(shù)。而且由上式為一平方數(shù)可得到

Π(a,b∈S),(a-bαi)

在Z[αi]中也為一平方數(shù)β2(證明方法見

F1(a,b)F2(a,b)≤2dN2/dUd+1

(2)在

從上表我們可以看出:當(dāng)分解80～110位十進制整數(shù)時,d的取值應(yīng)為4;當(dāng)分解

120～220位十進制整數(shù)時,d的取值應(yīng)為5;當(dāng)分解220～300位十進制整數(shù)時,d的取值應(yīng)為6。

六：數(shù)域篩選實現(xiàn)

素數(shù)產(chǎn)生器，用來產(chǎn)生素數(shù)，產(chǎn)生素數(shù)的大小根據(jù)用戶輸入的素數(shù)長度隨機產(chǎn)生，素數(shù)的長度以bit為單位。產(chǎn)生素數(shù)的算法由java.math.BigInteger類的靜態(tài)方法probablePrime(intbitLength,Randomrnd)提供。其中bitLength為產(chǎn)生素數(shù)的長度，rnd是一個隨機數(shù)，保證素數(shù)產(chǎn)生的隨機性。用MillerRabin算法可以判斷一個數(shù)是否為素數(shù)。MillerRabin在java.math.BigInterger類中封裝，booleanisProbablePrime(intcertainty)方法提供了判斷一個素是否為素數(shù)。certainty-調(diào)用方允許的不確定性的度量。假使該調(diào)用返回true，則此BigInteger是素數(shù)的概率超出(1-1/2certainty)。此方法的執(zhí)行時間

與此參數(shù)的值是成比例的。該方法可以在多項式時間內(nèi)判斷一個數(shù)是否為素數(shù)，從而保證RSA算法的可行行。

圖6-1

圖6-2產(chǎn)生兩個64bit的素數(shù)，并在文本框上顯示它們的乘積：

圖6-2

有了兩個素數(shù)的乘積，接下來就是如何分解。把一個數(shù)分解成兩個素數(shù)的乘積用的是二次篩選。二次