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 .