Abstract
This paper reports on the computation of a discrete logarithm in the finite
field $\mathbb F_{2^{30750}}$, breaking by a large margin the previous record,
which was set in January 2014 by a computation in $\mathbb F_{2^{9234}}$. The
present computation made essential use of the elimination step of the
quasi-polynomial algorithm due to Granger, Kleinjung and Zumbr\"agel, and is
the first large-scale experiment to truly test and successfully demonstrate its
potential when applied recursively, which is when it leads to the stated
complexity. It required the equivalent of about 2900 core years on a single
core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is
comparable to the approximately 3100 core years expended for the discrete
logarithm record for prime fields, set in a field of bit-length 795, and
demonstrates just how much easier the problem is for this level of
computational effort. In order to make the computation feasible we introduced
several innovative techniques for the elimination of small degree irreducible
elements, which meant that we avoided performing any costly Gr\"obner basis
computations, in contrast to all previous records since early 2013. While such
computations are crucial to the $L(\frac 1 4 + o(1))$ complexity algorithms,
they were simply too slow for our purposes. Finally, this computation should
serve as a serious deterrent to cryptographers who are still proposing to rely
on the discrete logarithm security of such finite fields in applications,
despite the existence of two quasi-polynomial algorithms and the prospect of
even faster algorithms being developed.