離散對數的強韌性如何高飛_(2n)GF(2n)GF(2^n)?
“正常”基於離散對數的密碼系統（DSA、Diffie-Hellman、ElGamal）在整數模一個大素數的有限域中工作 $ p $ . 但是，還存在其他有限域，尤其是二進制域 $ GF(2^n) $ . Coppersmith 描述了一種針對二進制域中離散對數的特定攻擊，後來被 Adleman 和 Huang改進為更通用的Function Field Sieve 。Joux 和 Lercier 使用 FFS 來獲取目前記錄 $ GF(2^n) $ 離散對數，其中 $ n = 613 $ .
我想知道的是：
- 離散對數如何在 $ GF(2^n) $ 與以素數為模的離散對數比較 $ p $ 的 $ n $ 位？在 Coppersmith 發表他的算法時，它使二進制域中的離散對數看起來比它的素數更容易 $ p $ 對應，但後者後來也得到了改進。
- 是否重要，對於離散對數 $ GF(2^n) $ ， 無論 $ n $ 本身是否素數？目前的記錄是 $ GF(2^{613}) $ ，打破了之前的記錄 $ GF(2^{607}) $ , 607 和 613 都是素數。將離散對數 $ GF(2^{1024}) $ 比在容易 $ GF(2^{1021}) $ ?
離散對數 $ \mathbb{F}_{p} $ 與一般數的整數分解具有相同的漸近複雜度： $ L_p[1/3,1.923] $ 對於一般整數， $ L_p[1/3,1.587] $ 對於特殊整數。離散對數 $ \mathbb{F}_{p^n} $ 具有與分解特殊整數相同的漸近複雜度，即 $ L_{p^n}[1/3, 1.587] $ ，通過函式場篩。
所以，從保理記錄推斷，我們可以用手揮動一個離散的登錄 $ \mathbb{F}_{2^{1021}} $ 比離散對數模一個 768 位一般素數容易一個數量級，並且與模一個偽梅森素數大致相同 $ 2^{1021} - c $ .
至於復合學位擴展領域是否更容易解決，也許。可以以多種方式表示相同的複合欄位（通常稱為欄位塔），並且某些表示可能比其他表示允許更快的中斷。這是 Andrew Odlyzko 1985 年論文離散對數及其密碼學意義的引述：
事實上，這些領域可能非常弱，因為在領域和它的子領域之間移動的可能性。
然而，沒有數據表明復合度數相對於素數度數的顯著漸近優勢（如果有的話，基於配對的方案將是敬酒，因為嵌入度數基本上是複合的）。
一個人也不應該忘記檢查平滑度 $ p^n-1 $ ，以避免令人尷尬的 Pohlig-Hellman 中斷。
2013 年 5 月更新
看來複合度確實弱於素度。Göloğlu et al和Joux攻擊領域的最新成果 $ \mathbb{F}_{2^n} $ , 對於復合 $ n $ ，比上面提到的函式域篩快得多。有關更多資訊，請參閱此問題。