離散對數(shù)求解算法

莊金成， 朱玉清

(1. 山東大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院/密碼技術(shù)與信息安全教育部重點實驗室， 山東 青島 266237； 2. 北京交通大學(xué) 智能交通數(shù)據(jù)安全與隱私保護(hù)技術(shù)北京市重點實驗室/計算機(jī)與信息技術(shù)學(xué)院， 北京 100044)

1 離散對數(shù)問題定義和應(yīng)用

1.1 離散對數(shù)問題和應(yīng)用

一般地，給定一個代數(shù)系統(tǒng)G(運算記作乘法)，元素g和冪數(shù)x，指數(shù)運算是計算gx。指數(shù)運算的逆運算是對數(shù)運算，即給定元素g,h∈G，求x使得gx=h，或者證明這樣的x不存在。

特別地，當(dāng)冪數(shù)屬于一個離散集合(常用的是整數(shù)集合)時，對應(yīng)的運算稱為離散指數(shù)運算，對應(yīng)的逆問題稱為離散對數(shù)問題。本文主要討論基于有限群的離散對數(shù)問題，基本的情形定義如下：給定一個有限群G，|G|=N以及元素g,h∈G，求解整數(shù)0≤x≤N-1使得gx=h，整數(shù)x稱為h相對于g的離散對數(shù)，也記為loggh。

離散對數(shù)問題本身是算法數(shù)論中的一個重要研究問題。Gauss證明模任意素數(shù)p存在原根，對應(yīng)的指標(biāo)求解問題就是一類重要的離散對數(shù)問題，在求解高次同余方程中有重要應(yīng)用。和通常的對數(shù)一樣，通過預(yù)先計算的離散對數(shù)可以將對應(yīng)的乘法運算轉(zhuǎn)化為加法運算。在通常離散對數(shù)定義變形得到的Zech對數(shù)(也稱Jacobi對數(shù))也有很多應(yīng)用[1]。

離散對數(shù)問題在密碼學(xué)中可以應(yīng)用于線性反饋移位寄存器的生成序列和相關(guān)的偽隨機(jī)數(shù)生成器[2]。1976年，Diffie等[3]提出了公鑰密碼學(xué)的概念，設(shè)想基于陷門單項函數(shù)設(shè)計公鑰密碼體制，并且在Gill的建議下采用模指數(shù)運算(其逆函數(shù)即為離散對數(shù))為設(shè)想的單向陷門函數(shù)，在此基礎(chǔ)上設(shè)計了第一個公鑰密碼系統(tǒng)，即Diffie-Hellman密鑰交換體制。1978年，Rivest等[4]基于整數(shù)分解問題設(shè)計了第一個公鑰加密和數(shù)字簽名體制。離散對數(shù)和整數(shù)分解問題是經(jīng)典的公鑰密碼體制中使用最廣的2類困難問題，并且2者的求解算法有很多相似之處。

Diffie-Hellman密鑰交換體制優(yōu)勢之一是提供了前向安全性[5]，此后離散對數(shù)問題被用來設(shè)計功能更豐富的密碼體制。例如，ElGamal[6]基于離散對數(shù)問題設(shè)計了公鑰加密方案，Schnorr[7]基于離散對數(shù)問題設(shè)計了身份認(rèn)證和簽名方案，美國國家技術(shù)標(biāo)準(zhǔn)局[8]基于離散對數(shù)制定了數(shù)字簽名標(biāo)準(zhǔn)。此外，Diffie-Hellman體制和ElGamal體制的設(shè)計思路還對后量子密碼方案的設(shè)計有所啟發(fā)，如基于編碼的密碼方案[9]、基于格上困難問題的LPR加密方案[10]。

公鑰密碼學(xué)中最早使用的離散對數(shù)問題是基于有限域的乘法群，后來擴(kuò)展到基于其他代數(shù)的結(jié)構(gòu)，包括基于橢圓曲線上有理點的加法群、基于超橢圓曲線的Jacobian、基于代數(shù)數(shù)域的理想類群和基于特定代數(shù)整數(shù)環(huán)等[11]。其中，基于橢圓曲線的離散對數(shù)問題應(yīng)用尤其廣泛，具體定義是給定有限域q上的橢圓曲線E和有理點P,Q∈P，求解整數(shù)x使得Q=xP。Miller[12]和Koblitz[13]獨立地提出基于橢圓曲線離散對數(shù)問題的密碼學(xué)方案設(shè)計。橢圓曲線離散對數(shù)問題還應(yīng)用在SM2、SM9和一些基于區(qū)塊鏈技術(shù)的協(xié)議等密碼方案中。

1.2 離散對數(shù)問題變體

根據(jù)不同的應(yīng)用場景，上述基本的離散對數(shù)問題有一些變體。

在一些應(yīng)用中可能限定離散對數(shù)的取值范圍，或者通過側(cè)信道等技術(shù)獲得部分信息從而縮小了求解范圍。例如，如果已知離散對數(shù)0≤x

如果已知離散對數(shù)x的二進(jìn)制中1的個數(shù)較少，對應(yīng)的稱為低Hamming重量離散對數(shù)問題。

如果給定一個生成元g和多個目標(biāo)元素h1,h2,…,hn，對應(yīng)的稱為多目標(biāo)離散對數(shù)問題。

如果給定多個生成元素g1,g2,…,gn和一個目標(biāo)元素h，對應(yīng)的稱為高維離散對數(shù)問題，也稱為表示問題[14]，可以應(yīng)用于設(shè)計電子貨幣等。

實例壓縮問題是指給定m個實例(gx1,gx2,…,gxm)，是否可以壓縮到n(n

離散對數(shù)問題還有一種變體稱為帶輔助輸入的離散對數(shù)問題，即在具有輔助輸入gx,gx2,…,gxd的情形下加速離散對數(shù)x的計算。

1.3 離散對數(shù)問題擴(kuò)展

Diffie和Hellman設(shè)計的兩方密鑰交換協(xié)議基于的更精確的困難問題是Diffie-Hellman問題，隨機(jī)選擇整數(shù)a,b,c，計算版本的定義是給定g,ga,gb，計算gab。 判定版本是區(qū)分ga,bb,bab與ga,bb,gc?；贒iffie-Hellman問題可以實現(xiàn)密鑰交換協(xié)議，如基于身份的加密[15]、陷門函數(shù)[16]等。

離散對數(shù)問題和Diffie-Hellman問題之間是否等價是一個重要的公開問題。

Diffie-Hellman問題的一個重要推廣是基于雙線性對的雙線性Diffie-Hellman問題[17]。給定素數(shù)階循環(huán)群G1,G2,G3，密碼學(xué)中的雙線性對是指存在如下映射

e:G1×G2→G3，

滿足雙線性、非退化和易于計算的性質(zhì)。密碼學(xué)中常用的雙線性對實例包括有限域橢圓曲線上的Weil對和Tate對。雙線性對密碼學(xué)包含了豐富的密碼功能，包括3方的一輪密鑰交互[18]，基于身份的加密[19]、短簽名[20]和群簽名[21]等。

Boneh等[22]設(shè)想了基于多線性映射可以設(shè)計功能更加豐富和強(qiáng)大的密碼體制。

2 通用求解算法

2.1 隨機(jī)自歸約和比特困難性

在密碼學(xué)應(yīng)用中更多是按照一定的分布隨機(jī)選擇平均情況的實例，平均情形的困難性和最壞情形困難性的關(guān)系對于密碼應(yīng)用具有重要意義。

離散對數(shù)問題通過隨機(jī)化方法可以建立最壞情況到一般情況的自歸約[23]。假定要求的目標(biāo)元素是h∈G=，可以選取隨機(jī)數(shù)rmodN，計算平均情形的實例h′=hgr，如果可以求解logh′，就可以對應(yīng)求解出logh。

一些格上的困難問題也可以建立最壞情況到一般情況的歸約，如最小整數(shù)解問題(Short Integer Solution，SIS)和容錯學(xué)習(xí)問題(Learning With Errors, LWE)。區(qū)別是離散對數(shù)是同一個群上的歸約，而后者是從任意的格歸約到給定的平均情形困難問題。

考慮一般循環(huán)群上的離散對數(shù)問題，如果G=g上的離散對數(shù)是困難的，Hastad等[24]證明對于隨機(jī)選取的滿足|G|=q=p′2k,q的二進(jìn)制表示為n比特，那么x的k到n-1比特以很高的概率是求解困難的。

2.2 量子算法

整數(shù)分解問題和離散對數(shù)問題既是公鑰密碼學(xué)應(yīng)用最廣泛的2類困難問題，針對2者的求解算法也有相似之處，包括量子算法和經(jīng)典算法。Shor[25]設(shè)計了量子算法求解整數(shù)分解問題和素域上的離散對數(shù)問題。

2者都可以看作特殊的隱藏子群問題，例如，基于有限循環(huán)群上的離散對數(shù)計算等價于求解下面映射的核：

φ:2→G，

其中，φ(a,b)=gahb。

更一般地，求解基于交換群的隱藏子群問題有高效的量子算法[26]。

下面討論經(jīng)典計算模型(如Turing機(jī))下求解離散對數(shù)問題的算法。

2.3 Pohlig-Hellman方法

2.4 小步-大步法

Shanks[28]利用時間-空間折中的思想設(shè)計了求解離散對數(shù)的小步-大步法，該方法是確定性求解算法，而且漸進(jìn)復(fù)雜度優(yōu)于窮搜法。

x=am+b,0≤a,b

為了求解對應(yīng)的a,b，注意到有等式(碰撞)

gb=hg-am。

可以通過尋找碰撞的方法求解。首先，計算(b,gb),0≤b

2.5 低存儲的概率算法

為了降低空間復(fù)雜度，可以采用偽隨機(jī)游走等方法設(shè)計概率求解算法。

2.5.1 Pollard Rho方法

針對基本的離散對數(shù)問題，Pollard[31]基于生日碰撞的思想設(shè)計了Rho方法。假設(shè)找到碰撞

ga1hb1=ga2hb2，

從而

(b1-b2)x≡a2-a1(modN)。

如果gcd(b1,b2,N)=1，那么可以求解x。

為了能夠以較低的空間找到所需的碰撞，Rho方法結(jié)合了偽隨機(jī)游走和Floyd尋找碰撞的技術(shù)。Pollard將G劃分成3個互不相交的集合G1,G2,G3。選定初始值s0=ga0hb0，定義如下偽隨機(jī)游走序列si=gaihbi,

對應(yīng)的可以得到(ai+1,bi+1)的迭代公式。為了找到碰撞sm=sn,m≠n，在第i步保存信息(si,ai,bi,s2i,a2i,b2i)并判斷是否si=s2i。

研究者后續(xù)提出了針對Rho方法的許多改進(jìn)，包括采用并行計算、群的劃分以及使用其他形式的隨機(jī)游走等。

2.5.2 Pollard袋鼠算法與Gaudry-Schost方法

針對小區(qū)間離散對數(shù)問題0≤x

在袋鼠算法中有2類游走，一類是家袋鼠游走gai，另一類是野袋鼠游走h(yuǎn)gbi。與Rho方法中的游走類似的是，Lambda方法中袋鼠的游走是由現(xiàn)在的值所對應(yīng)的分類決定；不同的是，步長按照預(yù)計算的一些小步?jīng)Q定。

Van Oorschot和Wiener使用了區(qū)分點技術(shù)來降低存儲，王瑤等[33]通過將一次大整數(shù)乘法分解為多次小整數(shù)乘法提高運算效率。

針對高維離散對數(shù)問題，Gaudry等[34]用偽隨機(jī)游走結(jié)合區(qū)分點的算法。

2.6 一般群模型和計算下界

上述算法沒有利用群的任何其他性質(zhì)，因此，對所有抽象群都適用。

Bartusek等[39]指出在通用群模型下，群的生成元是固定的，或者是隨機(jī)影響到離散對數(shù)問題和DH問題的求解下界。

3 指標(biāo)計算框架

根據(jù)上述結(jié)論可知，為降低算法復(fù)雜度的數(shù)量級，需要利用群的具體特性。注意到，離散對數(shù)滿足如下等式：

logg(h1h2)=logg(h1)+logg(h2)。

該性質(zhì)啟發(fā)我們求解離散對數(shù)的時候，不止需要考察元素本身，也需要考察元素的分解情況。如果能賦予群元素一種“大小”關(guān)系，并且能夠用某種方法將“較大”元素表示成“較小”元素的乘積，那么就可以從“較小”元素的離散對數(shù)恢復(fù)出“較大”元素的離散對數(shù)。特別地，當(dāng)群中的元素可以自然地看成(代數(shù))整數(shù)或者有限域上的多項式時，可以用范數(shù)或多項式的次數(shù)來描述元素的大小關(guān)系。

上述思想已經(jīng)體現(xiàn)在早期相關(guān)的工作中，并逐步發(fā)展完善，基于上述基本思想設(shè)計了指標(biāo)計算框架，應(yīng)用于整數(shù)分解、有限域和超橢圓曲線離散對數(shù)求解等。而對于橢圓曲線，目前暫未找到比較好的指標(biāo)計算方法。

3.1 光滑性和概率

指標(biāo)計算方法中的一個基本概念是(在合適范數(shù)下的)光滑性，其刻畫一個“較大”元素是否能表示成一些“較小”元素的乘積。

3.2 指標(biāo)計算框架

指標(biāo)計算框架一般包括如下3個部分：

(1)確定因子基(也稱光滑基)。根據(jù)具體的問題參數(shù)確定因子基S={s1,s2,…,sk}?G，例如，選定光滑界b之后所有b-光滑的元素添加g的集合。

(2)求解因子基元素離散對數(shù)。首先需要生成關(guān)系式，考察同態(tài)映射：

φ:k→G,

e11loggs1+…+e1kloggsk=0modN。

因此，通過關(guān)系式就得到了一個以因子基元素離散對數(shù)為變量的線性同余方程。

當(dāng)收集到足夠多的關(guān)系式，就可以求解線性同余方程組，得到因子(后面都統(tǒng)一成因子基)基元素的離散對數(shù)。

在實際求解過程中，所得到線性同余方程往往是稀疏的，可以采用比消元法更快的求解算法，如Wiedemann算法[43]。

(3)目標(biāo)元素離散對數(shù)。給定目標(biāo)元素h，為了求解這個元素的離散對數(shù)，可以通過一定的方法將該元素(可以是該元素的方冪)表示為因子基元素的組合。從而可以由因子基元素的離散對數(shù)推導(dǎo)出目標(biāo)元素的離散對數(shù)。

4 有限域離散對數(shù)求解

有限域上的任意函數(shù)可以表示稱為多項式的形式，特別地，有限域上的離散對數(shù)看作一個函數(shù)也有多項式表示[44-49]，但是直接使用多項式計算離散對數(shù)的效率并不高。

針對有限域的具體表示，可以結(jié)合指標(biāo)計算框架設(shè)計比通用求解算法更高效的方法，記

LQ(α,c)=exp((c+o(1))(logQ)α(loglogQ)1-α),

其中，0≤α≤1,c是一個常數(shù)，有時簡記為LQ(α)或者L(α)。

4.1 有限域按照特征的分類

令Q=pn表示有限域pn的元素個數(shù)，考慮當(dāng)參數(shù)趨于無窮的情況，隨著Q→∞特征p=LQ(αp,cp)。

如果αp>1/3，稱為中等特征或大特征有限域，目前最快的求解算法是數(shù)域篩法[50-53]，時間復(fù)雜度是亞指數(shù)時間；如果αp<1/3，稱為小特征的情況，目前最快的求解算法漸進(jìn)時間復(fù)雜度為準(zhǔn)多項式時間[54-57]。

4.2 中等和大特征有限域離散對數(shù)

數(shù)域篩法是在指標(biāo)計算框架的基礎(chǔ)上，結(jié)合中等和大特征有限域的具體表示設(shè)計的，其將有限域提升到數(shù)域中，利用數(shù)域中元素的范數(shù)來確定元素的大小。數(shù)域篩法包括多項式選取、因子基離散對數(shù)求解和目標(biāo)元素離散對數(shù)求解。設(shè)目標(biāo)有限域為pn。

(1)在多項式選取階段，需要選取2個整系數(shù)的不可約多項式f(x)和g(x)，使得它們的模p有n次不可約公因式ψ(x)。這樣可以得到上的2個數(shù)域Kf和Kg，如圖1所示。

圖1 數(shù)域構(gòu)造Fig.1 Construction of number fields

圖2 數(shù)域篩法Fig.2 The number field sieve

對于一個整系數(shù)多項式，可以分別將其看成Kf和Kg中的元素，并且通過有限域pn聯(lián)系起來。

(2)在因子基元素離散對數(shù)階段，需要根據(jù)具體參數(shù)選取合適的因子基，通過篩法求解出相應(yīng)的離散對數(shù)。

由于數(shù)域中只存在素理想的唯一分解，因此，取因子基為一些范數(shù)較小的素理想。這里以篩1次多項式為例，此時取因子基為范數(shù)不超過B的1次素理想。

在給定范圍內(nèi)篩(a,b)對，希望多項式a+bx在Kf和Kg中同時B-光滑，即a+bx在Kf和Kg中生成的主理想能同時分解成因子基中素理想的乘積。這樣便得到了因子基元素之間的一個同余方程。接著利用λ映射[51]，將素理想之間的關(guān)系方程轉(zhuǎn)化成元素之間的關(guān)系方程。當(dāng)?shù)玫阶銐蚨嗟年P(guān)系方程后，通過解方程便可得到因子基元素的離散對數(shù)。

需要注意的是，對于中等特征有限域，通常篩1次多項式是不夠的，還需要篩高次多項式。此時因子基也需要包含相應(yīng)的高次素理想。

(3)在目標(biāo)元素離散對數(shù)求解階段，需要在前2步的基礎(chǔ)上求解給定的目標(biāo)元素離散對數(shù)。這一步又可以分為2個階段：光滑化階段和遞降階段。

在光滑化階段，通過將目標(biāo)元素隨機(jī)化，期待其較為光滑，即希望目標(biāo)元素能分解成若干范數(shù)較小的元素。在遞降階段，將上述范數(shù)較小的元素通過格篩的方法進(jìn)一步降低其范數(shù)，使其歸約到因子基元素中，從而恢復(fù)出對應(yīng)的離散對數(shù)。

數(shù)域篩法的漸進(jìn)復(fù)雜度為L(1/3,c)，在實際使用中，計算因子基離散對數(shù)是其最耗時的部分。目前，數(shù)域篩法的改進(jìn)均集中在第二個參數(shù)c上。

由于數(shù)域定義多項式的性質(zhì)將影響被篩元素的光滑概率，從而影響算法的復(fù)雜度，研究者提出了多種不同的多項式選取方法[52,58-60]。特別地，當(dāng)有限域的特征滿足某些特定條件時，可以構(gòu)造出性質(zhì)更好的多項式，這類方法稱為特殊數(shù)域篩法[61-62]。

有別于僅構(gòu)造2個數(shù)域，研究者發(fā)現(xiàn)可以利用多個數(shù)域提高關(guān)系方程的收集效率，這類方法稱為多重數(shù)域篩法[63-65]。

如果構(gòu)造的數(shù)域具有非平凡的自同構(gòu)，可以利用自同構(gòu)將因子基中元素劃分成等價類，從而減少所需計算的因子基離散對數(shù)數(shù)目[52,59]。

當(dāng)有限域的擴(kuò)張次數(shù)大于1時，可以利用有限域的真子域構(gòu)造范數(shù)較小的等價元素，以提高目標(biāo)元素的光滑概率，從而降低光滑化階段的復(fù)雜度[67-69]。

在遞降階段，除了常用的一次素理想外，也可以使用高次素理想來提高計算效率[69-70]。

目前，計算素域中離散對數(shù)的記錄由Boudot等[71]保持，他們使用數(shù)域篩法計算了整數(shù)模795比特安全素數(shù)的素域中的離散對數(shù)問題。值得注意的是，F(xiàn)ried等[72]在此之前計算了1 024比特素域中的離散對數(shù)，不過這里選取的素域適用于特殊數(shù)域篩法，并且其有160比特的子群。

4.3 小特征有限域離散對數(shù)

早期求解小特征有限域離散對數(shù)較快的算法是在指標(biāo)計算框架基礎(chǔ)上發(fā)展出的函數(shù)域篩法[73-76]。函數(shù)域篩法與數(shù)域篩法類似，只不過將有限域提升到函數(shù)域，用多項式的次數(shù)代替之前數(shù)域中元素的范數(shù)來確定元素的大小。

原始的函數(shù)域篩法過于技術(shù)性，Joux等[76]在2006年給出了簡化版本。算法的框架如圖3所示：

圖3 函數(shù)域篩法Fig.3 The function field sieve

函數(shù)域篩法的流程與數(shù)域篩法類似，不同的是，此時處理對象是函數(shù)域中的多項式而不是數(shù)域中的代數(shù)整數(shù)，這里省略算法細(xì)節(jié)。

在2013年，Joux[77]提出了小特征有限域的Frobenius表示，并且提出了復(fù)雜度為L(1/4)的求解算法。此后又進(jìn)一步改進(jìn)得到準(zhǔn)多項式時間的BGJT算法。

(1)構(gòu)造有限域的Frobenius表示。為此，需要將給定的有限域嵌入到合適的擴(kuò)域：

pk

→

qk

→

q2k

,

這里，q=pr,r=「logpk?。

搜索低次數(shù)多項式h0,h1∈q2[x] 使得存在不可約因子：

f(x)|h1(x)xq-h0(x),

其中，f(x)∈q2[x]，并且deg(f(x))=k。

該性質(zhì)有利于提高后續(xù)產(chǎn)生關(guān)系式的效率。但是，Cheng等[78]指出采用這種表示本質(zhì)上是在剩余類環(huán)q2[x]/(h1(x)xq-h0(x))上做運算，需要處理零因子的影響。

(2)假設(shè)選取相對于ζ次數(shù)為1的有限域元素為因子基元素。為了求解因子基元素的離散對數(shù)，注意到有恒等式：

應(yīng)用Mobius 變換

x

去掉分母后得到

(cζ+d)(aζ+b)q)-(aζ+b)(cζ+d)q。

根據(jù)q-次方冪的性質(zhì)得到

(cζ+d)(aqζq+bq)-(aζ+b)(cqζq+dq)。

根據(jù)構(gòu)造有ζq=h0(ζ)/h1(ζ),帶入上式得

(aqh0(ζ)+bqh1(ζ))(cζ+d)-

(aζ+b)(cqh0(ζ)+dqh1(ζ))。

注意到上式2邊相對于ζ的次數(shù)都不高，因此有較高的概率2邊都分裂成一次元素的乘積。

為了得到不同的關(guān)系式，需要選取子群PGL(2,q) 在群PGL(2,q2)中不同陪集的代表元[79]。

(3)假設(shè)目標(biāo)元素是W(ζ)∈q2k[ζ],W相對于ζ的次數(shù)大于1。

類似地，考慮恒等式：

然后應(yīng)用變量替換

x

帶入并展開后可得左邊是W相關(guān)的元素乘積，如果右邊是deg(W)/2光滑的，就得到一個關(guān)系式。收集到足夠多的關(guān)系式之后，可以將W約化到deg(W)/2光滑的元素。通過迭代，可以歸約到因子基元素的離散對數(shù)。

針對小特征有限域離散對數(shù)時間復(fù)雜度較低的求解算法有的依賴于一些啟發(fā)式假設(shè)，一些改進(jìn)工作旨在探索是否可以減少或者替換啟發(fā)式假設(shè)，比如概率算法[57]和確定性算法[80]。

目前，小特征有限域離散對數(shù)的計算記錄由Granger等[81]保持，他們求解了30 750比特二元域中的離散對數(shù)。

5 橢圓曲線離散對數(shù)求解

其中，q+1-NE稱為E的跡。

5.1 一般橢圓曲線

針對一般的橢圓曲線離散對數(shù)問題，目前通用求解方法仍是最優(yōu)的計算橢圓曲線離散對數(shù)的方法。為了減少空間復(fù)雜度，經(jīng)常采用的是基于偽隨機(jī)游走的方法，例如，Pollard方法和Gaudry-Schost方法等。李俊全等[84]研究了迭代函數(shù)的設(shè)計準(zhǔn)則，并且給出了一個改進(jìn)的并行碰撞算法。

但是結(jié)合橢圓曲線的性質(zhì)，可以做一些改進(jìn)。例如，Gallant等[85]和Wiener等[86]提出利用自同構(gòu)將群元素劃分成等價類，從而提高算法效率。Galbraith等[87]利用橢圓曲線易于求逆的性質(zhì)對區(qū)間離散對數(shù)求解進(jìn)行加速，Zhu等[88]在此基礎(chǔ)上進(jìn)一步做出了改進(jìn)。Zhang等[89]用二元域上橢圓曲線的半點運算比倍點運算更快的特點加速離散對數(shù)的求解。Wu等[90]給出了Gaudry-Schost算法的一個漸近時間復(fù)雜度最優(yōu)的改進(jìn).

5.2 歸約到有限域

5.2.1 歸約到有限域乘法群

Meneze等[91]和Frey等[92]利用雙線性映射工具提出了一種約化方法，將橢圓曲線離散對數(shù)問題歸約到有限域的適當(dāng)擴(kuò)域qk上的離散對數(shù)問題，然后利用計算有限域離散對數(shù)的更高效的求解方法。這里的k稱為曲線的嵌入次數(shù)，其通常很大，因此該方法僅對少數(shù)曲線有效。特別地，當(dāng)曲線的跡被p整除時，這類曲線稱為超奇異橢圓曲線，其嵌入次數(shù)不超過6，極易受到這類方法攻擊。

針對特殊的參數(shù)，文獻(xiàn)[93-94]考察了有限域離散對數(shù)問題和橢圓曲線離散對數(shù)問題的關(guān)系。

5.2.2 歸約到有限域加法群

如果橢圓曲線滿足NE=q，即跡為1，稱為異常橢圓曲線。特別地，當(dāng)q=p為素數(shù)時,這類曲線的點群恰好是素數(shù)階的，似乎滿足密碼學(xué)的要求。但是異常橢圓曲線離散對數(shù)問題卻是十分容易的，Smart[95]、Satoh等[96]、Semaev[97]分別獨立給出了高效求解算法。前2者是一種提升方法，針對素域的情形，將曲線提升到p進(jìn)數(shù)域p中，利用形式對數(shù)將橢圓曲線的點群歸約成有限域的加法群。之后朱玉清等[98]拓展了提升方法的使用范圍，可以求解一般有限域上橢圓曲線p-群中的離散對數(shù)問題。Semaev則是利用除子和微分形式空間的對應(yīng)，在固定點的取值將橢圓曲線離散對數(shù)問題歸約成有限域加法群中的離散對數(shù)問題。之后祝躍飛等[99]對其進(jìn)行優(yōu)化，給出了在無窮遠(yuǎn)點取值的方法，避免了在擴(kuò)域上進(jìn)行運算。

5.3 歸約到高虧格曲線

在橢圓曲線上直接設(shè)計指標(biāo)計算法并不容易(見下一小節(jié))，但對于虧格g≥2的光滑代數(shù)曲線C，存在指標(biāo)計算法可以有效地計算其雅可比Jac(C)中的離散對數(shù)。當(dāng)曲線是超橢圓曲線時，由于其雅可比中元素存在Mumford表示，即表示成2個次數(shù)較低的多項式，利用多項式的分解性質(zhì)可以給出亞指數(shù)時間的指標(biāo)計算法[100]。對于一般曲線，研究者利用“雙大素數(shù)”技巧給出了時間復(fù)雜度為O(q2-2/g)的算法，即使對于較小的虧格g，其效率也優(yōu)于Pollard rho算法[101-102]。

為了利用上述指標(biāo)計算法，自然的想法是將橢圓曲線離散對數(shù)歸約成代數(shù)曲線雅可比中的離散對數(shù)。為此，F(xiàn)rey等[103]提出了Weil下降方法，之后Galbraith等[104]對其進(jìn)行了完善。

設(shè)E是定義在擴(kuò)域qn上的橢圓曲線，曲線方程為f(X,Y)=0。取qn關(guān)于q的一組基{1,θ,θ2,…,θn-1}，令

X=X0+X1θ+…+Xn-1θn-1,Y=Y0+Y1θ+…+Yn-1θn-1,

則f(X,Y)=0可以表示成

∑fi(X0,…,Xn-1,Y0,…,Yn-1)θi=0，

其中，fi是q上多項式。通過這種方式，可以由qn的橢圓曲線得到q上的n維阿貝爾簇。如果能找到一條曲線C使得其雅可比Jac(C)包含該阿貝爾簇，則能將橢圓曲線的離散對數(shù)問題歸約成Jac(C)中的離散對數(shù)問題，再利用指標(biāo)計算法求解。

對于特征2有限域，Gaudry等[105]利用函數(shù)域的Artin-Schreier擴(kuò)張構(gòu)造了滿足條件的曲線，之后Diem[106]用Kummer擴(kuò)張給出了奇特征情形的構(gòu)造方式，這類構(gòu)造方法統(tǒng)稱為GHS攻擊。該攻擊對一些曲線取得了比較好的效果，但是對于大部分橢圓曲線而言，該方法得到的覆蓋曲線的虧格很高，其關(guān)于n是指數(shù)級的，導(dǎo)致效率并不比通用算法高。

5.4 基于求和多項式的指標(biāo)計算法

仿照第3節(jié)指標(biāo)計算法的框架，橢圓曲線離散對數(shù)的指標(biāo)計算流程如下：取定E(q)的某個子集為因子基；選取隨機(jī)的點R=aP+bQ，將其分解成因子基中點的和，即aP+bQ=∑eiPi，其中，Pi為因子基中元素；收集足夠多這樣的關(guān)系式，從而計算出Q關(guān)于P的離散對數(shù)。

對于有限域中的元素，其可以自然地提升到數(shù)域或者函數(shù)域，根據(jù)素理想或者多項式的唯一分解性可以分解成一些范數(shù)小或者次數(shù)低的元素。而對于橢圓曲線，如何定義因子基并給出有效的點分解算法是設(shè)計橢圓曲線指標(biāo)計算法的難點所在。為此，Semaev[107]提出了求和多項式。

(x1,y1)+(x2,y2)+…+(xm,ym)=O，

對于素域上的橢圓曲線，一般取因子基為x坐標(biāo)小于預(yù)先取定的正整數(shù)B的有理點全體。此時，為了得到點R=(xR,yR)與因子基元素的關(guān)系式，可以計算Sm(X1,X2,…,Xm-1,xR)=0中小于B的零點。若該方程存在零點，則說明可以找到點R與m-1個因子基元素的關(guān)系式。對于擴(kuò)域qn上的橢圓曲線，Gaudry[108]和Diem[109]取因子基為x坐標(biāo)落在qn的某個q子空間中的有理點全體。通過對Sm=0使用Weil限制，可以將qn上的方程轉(zhuǎn)換成子域q上n個代數(shù)方程，從而更易于計算。

然而計算上述代數(shù)方程(組)的零點通常并不容易，一般均需使用Gr?bner基算法，算法的時間復(fù)雜度為O(Nd)，其中，N為變量個數(shù)，d為正則次數(shù)。研究表明，這類方程的正則次數(shù)通常很高[110-111]。

為了提高求解求和多項式零點的效率，研究者嘗試?yán)们蠛投囗検降膶ΨQ性降低多項式的次數(shù)[112-113]，將求和多項式分裂成多個子求和多項式組，通過增加變量數(shù)目降低方程次數(shù)[114]，以及利用Frobenius映射加速方程的求解[115]。