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

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

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

黃敬騰

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

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

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ù)分解算法的不斷改進(jìn)和計(jì)算機(jī)運(yùn)算速度的加快,人們對(duì)RSA系統(tǒng)的安全性又產(chǎn)生了懷疑。在二戰(zhàn)期間,英國(guó)間諜運(yùn)用古老的大型計(jì)算機(jī)成功地破譯了大量的德國(guó)軍事情報(bào),為盟軍戰(zhàn)勝法西斯贏的了主動(dòng)。正是由于計(jì)算機(jī)的迅猛發(fā)展,加密與解密的對(duì)抗和數(shù)論自身理論的提高,整數(shù)分解的研究也就變得特別地活躍,算法不斷地得

到改進(jìn)。

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

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

二：RSA算法簡(jiǎn)介

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

a)隨機(jī)選取的在素?cái)?shù)P和Q，還有N，其中N=P*Q，P和Q保密，N

公開。

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

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

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

保密。

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

3．RSA算法的特點(diǎn)

a)RSA算法的特點(diǎn)是非對(duì)稱加密算法，通過兩個(gè)素?cái)?shù)P和Q產(chǎn)生公鑰(E,N)

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

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

鑰可以解迷。加密解密是非對(duì)稱的。

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

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

4．RSA算法的不足。

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

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

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

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

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

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

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

i)對(duì)所有(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)造實(shí)際上是不可約多項(xiàng)式f∈Z[x]的構(gòu)造。在實(shí)踐中,對(duì)于十進(jìn)制字1/3節(jié)在110～160之間的數(shù)n,宜取d=5。理論上d=((3

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

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

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

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

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

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

的作為我們的f。

四：數(shù)域篩選的多項(xiàng)式時(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:對(duì)于某個(gè)給定的平滑界B,我們收集互素的整數(shù)對(duì)(a,b),使之滿足:F1(a,b)和F2(a,b)為平滑B數(shù)。這時(shí)我們稱這樣的整數(shù)對(duì)為一個(gè)關(guān)系。通過線形代數(shù)的擴(kuò)張,在這大量的關(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位十進(jìn)制整數(shù)時(shí),d的取值應(yīng)為4;當(dāng)分解

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

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

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

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

圖6-1

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

圖6-2

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