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

莊金成， 朱玉清

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

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

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

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

特別地，當冪數(shù)屬于一個離散集合(常用的是整數(shù)集合)時，對應的運算稱為離散指數(shù)運算，對應的逆問題稱為離散對數(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存在原根，對應的指標求解問題就是一類重要的離散對數(shù)問題，在求解高次同余方程中有重要應用。和通常的對數(shù)一樣，通過預先計算的離散對數(shù)可以將對應的乘法運算轉化為加法運算。在通常離散對數(shù)定義變形得到的Zech對數(shù)(也稱Jacobi對數(shù))也有很多應用[1]。

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

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

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

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

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

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

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

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

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

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

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

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

Diffie和Hellman設計的兩方密鑰交換協(xié)議基于的更精確的困難問題是Diffie-Hellman問題，隨機選擇整數(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，密碼學中的雙線性對是指存在如下映射

e:G1×G2→G3，

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

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

2 通用求解算法

2.1 隨機自歸約和比特困難性

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

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

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

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

2.2 量子算法

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

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

φ:2→G，

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

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

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

2.3 Pohlig-Hellman方法

2.4 小步-大步法

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

x=am+b,0≤a,b

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

gb=hg-am。

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

2.5 低存儲的概率算法

為了降低空間復雜度，可以采用偽隨機游走等方法設計概率求解算法。

2.5.1 Pollard Rho方法

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

ga1hb1=ga2hb2，

從而

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

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

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

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

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

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

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

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

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

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

2.6 一般群模型和計算下界

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

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

3 指標計算框架

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

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

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

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

3.1 光滑性和概率

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

3.2 指標計算框架

指標計算框架一般包括如下3個部分：

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

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

φ:k→G,

e11loggs1+…+e1kloggsk=0modN。

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

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

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

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

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

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

針對有限域的具體表示，可以結合指標計算框架設計比通用求解算法更高效的方法，記

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

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

4.1 有限域按照特征的分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當有限域的擴張次數(shù)大于1時，可以利用有限域的真子域構造范數(shù)較小的等價元素，以提高目標元素的光滑概率，從而降低光滑化階段的復雜度[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ù)較快的算法是在指標計算框架基礎上發(fā)展出的函數(shù)域篩法[73-76]。函數(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ù)，這里省略算法細節(jié)。

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

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

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。

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

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

應用Mobius 變換

x

去掉分母后得到

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

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

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

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

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

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

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

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

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

類似地，考慮恒等式：

然后應用變量替換

x

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

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

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

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

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

5.1 一般橢圓曲線

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

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

5.2 歸約到有限域

5.2.1 歸約到有限域乘法群

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

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

5.2.2 歸約到有限域加法群

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

5.3 歸約到高虧格曲線

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

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

設E是定義在擴域qn上的橢圓曲線，曲線方程為f(X,Y)=0。取qn關于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ù)問題，再利用指標計算法求解。

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

5.4 基于求和多項式的指標計算法

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

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

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

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

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

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