Cryptology ePrint Archive: Report 2013/095

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)

Short URL: ia.cr/2013/095

Discussion forum: Show discussion | Start new discussion