学术报告（田松 3.18）

本报告介绍求解三次扩域GF(q^3)上椭圆曲线离散对数问题的新方法。

其思想是先利用从椭圆曲线的Weil restriction到基域GF(q)上雅可比簇的同源将离散对数问题转化为雅可比簇上离散对数问题，再对后者应用指标计算方法。新方法与覆盖攻击原理一样，不同之处在于没有显式地构造覆盖映射。

目前解GF(q^3)上素数阶椭圆曲线离散对数问题的最快算法是基于求和多项式的指标计算算法，其时间复杂度为\tilde{O}(q^{4/3}), 而新方法时间复杂度为\tilde{O}(q)。