**A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic**

*Antoine Joux*

**Abstract: **In this paper, we describe a new algorithm for discrete logarithms
in small characteristic. This algorithm is based on index calculus
and includes two new contributions. The first is a new method for
generating multiplicative relations among elements of a small
smoothness basis. The second is a new descent strategy that allows
us to express the logarithm of an arbitrary finite field element in
terms of the logarithm of elements from the smoothness basis. For a
small characteristic finite field of size $Q=p^n$, this algorithm
achieves heuristic complexity $L_Q(1/4+o(1)).$ For technical
reasons, unless $n$ is already a composite with factors of the right
size, this is done by embedding $\GF{Q}$ in a small extension
$\GF{Q^e}$ with $e\leq 2\lceil \log_p n \rceil$.

**Category / Keywords: **foundations / Number Theory, Discrete Logarithms

**Original Publication**** (in the same form): **Will appear in the proceedings of SAC 2013

**Date: **received 20 Feb 2013, last revised 24 Jul 2013

**Contact author: **antoine joux at m4x org

**Available format(s): **PDF | BibTeX Citation

**Version: **20130724:072923 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]