大整數分解算法綜述

楊江帥

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

0 引言

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

1 RSA密碼算法簡述

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

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

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

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

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

2 大整數分解算法介紹

2.1 試除法

2.2 蒙特卡洛方法

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

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

2.3 p-1方法

p-1方法[3]是POLLARD J M在1974年提出的分解整數的方法。假設當n有一個素因子p且p-1的素因子較小時，使用這種方法是比較有效的。p-1方法的分解原理來源于數論中的費馬小定理。設n是待分解的整數，p是n的一個素因子，根據費馬小定理，如果p-1|Q，則對于與n互素的整數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方法適合分解這一類合數n：包含一些素因子p，且使得p+1是由比較多的小素數相乘而得出的。

2.5 費馬分解法

2.6 連分數分解法

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

2.7 二次篩選法

2.8 橢圓曲線分解法

橢圓曲線分解法[7]是由荷蘭科學家LENSTRA H W于1987年提出的一種整數分解法，這種方法使用了橢圓曲線的群結構，隨機選取一條橢圓曲線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使用橢圓曲線方法成功分解了第十個和第十一個費馬數，Wagstaff于2012年使用此方法分解出了一個79位數的因子。

2.9 數域篩選法

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

3 大整數分解算法比較分析

4 結論

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