International Association
for Cryptologic Research

The discrete logarithm over finite fields of small characteristic

can be solved much more efficiently than previously thought.

This algorithmic breakthrough is based

on heuristic polynomial time algorithms to

compute the factor base discrete logarithm.

In this paper, we concentrate on the Kummer extension

$ \\F_{q^{2(q-1)}}. $ We design a new heuristic algorithm with

an improved bit complexity $ \\tilde{O}(q^{1+ \\theta} ) $ (or algebraic complexity

$\\tilde{O}(q^{\\theta} )$) to compute the discrete logarithms of elements in

a factor base of cardinality $q^2$, where $ \\theta < 2.373 $ is

the matrix multiplication exponent.

We reduce the correctness of the algorithm to a conjecture

concerning the determinant of a simple $ (q+1)-$dimensional lattice,

rather than to elusive smoothness assumptions.

We verify the conjecture numerically for all $ q $\'s such that

$ \\log_2(q^{2(q-1)}) \\leq 5000 $, and provide theoretical

supporting evidences.