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

2020-10-07 08:43:59

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]