30750位二进制域离散对数的计算

30750位二进制域离散对数Robert Granger和Thorsten Kleinsung以及Arjen K.Lenstra和Benjamin Wesolowski和Jens Zumbragel的计算摘要：本文报道了有限域$\mathbb{F}_{2^{30750}}$的离散对数的计算，大大打破了由$\mathbb{F}_{2^{9234}}$所创造的记录。本文的计算充分利用了Granger，Kleinsung和Zumr#aGel提出的拟多项式算法的消元步骤，是第一个真正测试并成功证明其递归应用潜力的大型实验，也就是当它导致规定的复杂性时。在运行频率为2.6 GHz的Intel Xeon Ivy Bridge处理器的单核上，它需要大约2900美元的核心年数，这与素数域的离散对数记录(位长为795美元)所花费的大约3100美元的核心年数相当，并证明了对于这种水平的计算工作，问题要容易得多。为了使计算可行，我们引入了几种消除小次数不可约元素的创新技术，这意味着我们避免了执行任何代价高昂的Gr#oobner基计算，这与2013年初以来的所有记录形成了鲜明对比。虽然这样的计算对于$L(\frac{1}{4}+o(1))$复杂性算法至关重要，但对于我们的目的来说，它们实在太慢了。最后，这种计算应该对密码学家起到严重的威慑作用，尽管存在两种准多项式算法，并且有可能开发出更快的算法，但密码学家仍然建议在应用中依赖于这种有限域的离散对数安全性。类别/关键词：公钥密码学/离散对数问题，有限域，二进制域，准多项式算法日期：2020年8月7日收到，最后一次修订时间：2020年8月7日联系作者：rSurrey ac UK的格兰杰，Thorsten kleinsung@epfl ch，Arjen Lenstra@epfl ch，Benjamin Wesolowski@mathu-Bordeaux fr，jens zumbraegel@uni-pasou de可用格式：pdf|BibTeX引文版本：20200811：114216(本报告的所有版本)[Cryptology Print Archive]