无特殊指数或特殊结构的二元域离散对数的复杂性

Question

最近，由于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$中)时间和内存复杂度指数的东西？

Answer 1

编辑：我认为最好的复杂性是指数的，这是不正确的。这实际上是准多项式(感谢塞缪尔·内维斯的评论)。

回顾Coppersmith的算法具有复杂性$$ L_{2^ n} (1/3，c) $$对于一个小常数$c，$即使对于$n$素数，这是最困难的情况，使用巴尔布列斯库等。阿尔-S法的$GF(2^n)$上的离散对数具有拟多项式复杂度$$ O(2^c( \log n)^2})不对称的{c\log n}。$$

注意，作者指出“L(1/4)算法与我们的拟多项式算法之间的交点尚未确定”。