沒有特殊指數或特殊結構的二進制域中離散對數的複雜性

最近有一些工作，由於 Joux、Gologlu、Zumbragel 和其他人開發了有效的算法，用於小（特別是二進制）特徵的離散對數，其中指數具有一些特殊形式。請參閱問題中的討論

GF(2^n) 中的離散對數如何強韌

和

do-recent-announcements-about-solving-the-dlp-in-gf26120-apply-to-schemes?noredirect=1&lq=1

我的理解是離散對數 $ \operatorname{GF}(2^n) $ 在哪裡 $ n $ 很大並且沒有什麼特別之處，因為它對攻擊仍然比較健壯。

這是問題，說我選擇 $ n $ 足夠大，使得乘法群 $ \operatorname{GF}(2^n)^{\ast} $ 沒有小的子群。所以要麼 $ 2^n-1 $ 是素數，或 $ n $ 是如此之大且選擇得當，以至於最大的子組足夠大。

在這種情況下，最好的算法仍然是離散對數的嬰兒步巨步嗎？或者其他仍然指數的東西（在 $ n $ ) 時間和記憶體複雜度？

**編輯：**我認為最好的複雜性是指數的預感是不正確的。它實際上是準多項式（感謝 Samuel Neves 的評論）。

回想一下 Coppersmith 的算法具有復雜性

$$ L_{2^n}(1/3,c) $$ 對於一個小常數 $ c, $ 而即使是 $ n $ 素數，這是最難的情況，離散對數超過 $ GF(2^n) $ 使用Barbulescu 等。al. 的方法 具有準多項式複雜度 $$ O(2^{c(\log n)^2})\asymp c’ n^{c \log n}. $$ 請注意，作者聲明“（之前最好的）L（1/4）算法和我們的準多項式算法之間的交叉點尚未確定”。

引用自：https://crypto.stackexchange.com/questions/56215