楊江帥

(中國(guó)電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所，北京 100083)

0 引言

大整數(shù)分解是數(shù)論中的一個(gè)基本問(wèn)題，從其誕生到現(xiàn)在已有數(shù)百年歷史，真正引起數(shù)學(xué)家、計(jì)算機(jī)科學(xué)家以及密碼學(xué)家的極大關(guān)注是近幾十年的事情，它不僅是公鑰加密算法RSA的最直接的攻擊手段，也是RSA安全性分析最關(guān)鍵的切入點(diǎn)，因而整數(shù)分解問(wèn)題的任何一點(diǎn)進(jìn)展都將引起密碼學(xué)界的關(guān)注。大數(shù)分解問(wèn)題既未被證明是多項(xiàng)式時(shí)間可解的P問(wèn)題，也未被證明是NP完備問(wèn)題，另外，大整數(shù)分解問(wèn)題的研究直接影響到數(shù)論及通信領(lǐng)域中其他一些問(wèn)題的解決，因而對(duì)其研究具有極其重要的理論意義和應(yīng)用價(jià)值。

1 RSA密碼算法簡(jiǎn)述

(1)選取大素?cái)?shù)p和q，計(jì)算模數(shù)n=pq和歐拉函數(shù)φ(n)=(p-1)(q-1)；

(2)選取一個(gè)和φ(n)互素的整數(shù)e作為公鑰,求出整數(shù)d作為私鑰，其中d滿足ed≡1(modφ(n))；

(3)將明文m加密：c=me(modn)，其中m滿足0

(4)將密文m加密：m=cd(modn)，其中c滿足0

由上述過(guò)程可知，如果能將算法中的模數(shù)n進(jìn)行分解，得到p和q，那么很容易將明文m恢復(fù)出來(lái)，因此，有效的大整數(shù)分解算法能夠破解RSA密碼算法。

2 大整數(shù)分解算法介紹

2.1 試除法

2.2 蒙特卡洛方法

蒙特卡洛方法[1]是一種基于隨機(jī)數(shù)序列的分解整數(shù)的方法，是由PALLARD J M于1975年提出的，該方法的基本思想如下：假設(shè)n是給定的待分解的整數(shù)，p是n的一個(gè)素因子。f(x)是整數(shù)環(huán)Z上的一元多項(xiàng)式。首先選擇隨機(jī)整數(shù)0

蒙特卡洛方法的實(shí)質(zhì)就是在一條擬隨機(jī)序列中找到兩個(gè)模p相等的整數(shù)，這個(gè)問(wèn)題與著名的生日問(wèn)題有關(guān)，也就是隨機(jī)選擇k個(gè)人，其中有兩個(gè)人是同一天生日的概率大于1/2，求k至少是多少，答案是k=23，與人們的直覺(jué)不一樣。同樣地，為了得到兩個(gè)整數(shù)模p同余的概率大于1/2，則至少需要的整數(shù)數(shù)目k應(yīng)滿足：

2.3 p-1方法

p-1方法[3]是POLLARD J M在1974年提出的分解整數(shù)的方法。假設(shè)當(dāng)n有一個(gè)素因子p且p-1的素因子較小時(shí)，使用這種方法是比較有效的。p-1方法的分解原理來(lái)源于數(shù)論中的費(fèi)馬小定理。設(shè)n是待分解的整數(shù)，p是n的一個(gè)素因子，根據(jù)費(fèi)馬小定理，如果p-1|Q，則對(duì)于與n互素的整數(shù)a，有p|aQ-1,因此d=gcd(aQ-1,n)>1，如果d

2.4 p+1方法

p+1方法[4]是WILLAMS H C于1982年提出的，p+1方法與p-1類似。Willams的p+1方法是通過(guò)對(duì)POLLARD J M的p-1方法做過(guò)詳細(xì)研究后并使用盧卡斯序列的等價(jià)于冪運(yùn)算的特性得到的。p+1方法適合分解這一類合數(shù)n：包含一些素因子p，且使得p+1是由比較多的小素?cái)?shù)相乘而得出的。

2.5 費(fèi)馬分解法

2.6 連分?jǐn)?shù)分解法

也就是說(shuō)(-1)m+1Qm是一系列模n的二次剩余。在這些二次剩余中，可以選出一些組成一個(gè)集合S，如果集合S中各個(gè)元素的乘積又剛好是一個(gè)完平方數(shù)，那么得到了一個(gè)形如a2≡b2(modn)的同余式，這樣也就得到了n的一個(gè)分解。

2.7 二次篩選法

2.8 橢圓曲線分解法

橢圓曲線分解法[7]是由荷蘭科學(xué)家LENSTRA H W于1987年提出的一種整數(shù)分解法，這種方法使用了橢圓曲線的群結(jié)構(gòu)，隨機(jī)選取一條橢圓曲線E:y2z=x3+axz2+bz3，如果(x,y,z)滿足該方程，且c≠0modp，則(cx,cy,cz)也滿足該方程，因此(x,y,z)和(cx,cy,cz)可以看成是等價(jià)的。用(x:y:z)表示包含(x,y,z)一類等價(jià)點(diǎn)的等價(jià)類。在這個(gè)群Ea,b中的加法零元O是(1:0:1)，此時(shí)z≡0(modp)，如果在某一步運(yùn)算中得到了加法零元O=(x,y,z)，那么通過(guò)計(jì)算gcd(z,n)得到了一個(gè)因子，可能將n分解。BRENT P R使用橢圓曲線方法成功分解了第十個(gè)和第十一個(gè)費(fèi)馬數(shù)，Wagstaff于2012年使用此方法分解出了一個(gè)79位數(shù)的因子。

2.9 數(shù)域篩選法

數(shù)域篩選法[8]是目前最快的整數(shù)分解算法，它是由POLLARD J M首先提出的。這個(gè)算法仍然是以解決a2≡b2(modn)為目的的，首先選取一個(gè)合適的整系數(shù)多項(xiàng)式f(x)和一個(gè)有理整數(shù)m，使得f(m)≡0(modn)，α是多項(xiàng)式f(x)的一個(gè)復(fù)根，可以定義一個(gè)從R=Z[α]到整數(shù)域的一個(gè)環(huán)同態(tài)：φ:R→Zn,φ(α)=m(modn)，則有:

3 大整數(shù)分解算法比較分析

4 結(jié)論

到目前為止，對(duì)于大整數(shù)分解問(wèn)題，大部分研究工作都是對(duì)現(xiàn)有算法的改進(jìn)，因此要找到新的算法，必須應(yīng)用新的理論知識(shí)。文獻(xiàn)[9]第一次將整數(shù)分解與二項(xiàng)式系數(shù)的和聯(lián)系在一起，雖然還沒(méi)有給出算法的復(fù)雜度分析，但卻給出了研究的新思路和新方向。另一方面，一些基于量子的整數(shù)分解算法充分利用了量子計(jì)算機(jī)強(qiáng)大的并行計(jì)算能力，使得大整數(shù)分解存在多項(xiàng)式時(shí)間算法，但現(xiàn)有的量子計(jì)算機(jī)尚不能實(shí)現(xiàn)有實(shí)際意義的量子算法。從總體上看，未來(lái)大數(shù)分解研究方向會(huì)在并行的前提下，盡可能提高系統(tǒng)效率，有可能是未來(lái)新的發(fā)展方向。