Welcome to the resource topic for 2013/095
Title:
A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic
Authors: 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.
ePrint: https://eprint.iacr.org/2013/095
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .