大整數(shù)分解算法綜述

楊江帥

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

0 引言

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

1 RSA密碼算法簡述

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

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

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

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

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

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

2.1 試除法

2.2 蒙特卡洛方法

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

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

2.3 p-1方法

p-1方法[3]是POLLARD J M在1974年提出的分解整數(shù)的方法。假設(shè)當n有一個素因子p且p-1的素因子較小時，使用這種方法是比較有效的。p-1方法的分解原理來源于數(shù)論中的費馬小定理。設(shè)n是待分解的整數(shù)，p是n的一個素因子，根據(jù)費馬小定理，如果p-1|Q，則對于與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方法是通過對POLLARD J M的p-1方法做過詳細研究后并使用盧卡斯序列的等價于冪運算的特性得到的。p+1方法適合分解這一類合數(shù)n：包含一些素因子p，且使得p+1是由比較多的小素數(shù)相乘而得出的。

2.5 費馬分解法

2.6 連分數(shù)分解法

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

2.7 二次篩選法

2.8 橢圓曲線分解法

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

2.9 數(shù)域篩選法

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

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

4 結(jié)論

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