Paper 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$.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Will appear in the proceedings of SAC 2013
- Keywords
- Number TheoryDiscrete Logarithms
- Contact author(s)
- antoine joux @ m4x org
- History
- 2013-07-24: revised
- 2013-02-21: received
- See all versions
- Short URL
- https://ia.cr/2013/095
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/095,
author = {Antoine Joux},
title = {A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/095},
year = {2013},
url = {https://eprint.iacr.org/2013/095}
}
