A finite field K admits a sparse medium subfield representation if

– it has a subfield of q^{2} elements for a prime power q, i.e. K is isomorphic to F_{q2k} with k ≥ 1;

– there exist two polynomials h_{0} and h_{1} over F_{q2} of small degree, such that h_{1}X^{q} − h_{0} has a degree k irreducible factor.

We shall assume that all the fields under consideration admit a sparse medium subfield representation. Furthermore, we also assume that the degrees of the polynomials h_{0} and h_{1} are uniformly bounded by a constant δ. Any finite field of the form F_{q2k} with k ≤ q + 2 admits a sparse medium subfield representation with polynomials h_{0} and h_{1} of degree at most 2.

In a field in sparse medium subfield representation, elements will always be represented as polynomials of degree less than k with coefficients in F_{q2}. When we talk about the discrete logarithm of such an element, we implicitly assume that a basis for this discrete logarithm has been chosen, and that we work in a subgroup whose order has no small irreducible factor to limit ourselves to this case.

Proposition: Let K = F_{q2k} be a finite field that admits a sparse medium subfield representation. Under the heuristics, there exists an algorithm whose complexity is polynomial in q and k and which can be used for the following two tasks.

1. Given an element of K represented by a polynomial P ∈ F_{q2}[X] with 2 ≤ deg P ≤ k − 1, the algorithm returns an expression of log P (X ) as a linear combination of at most O(kq^{2}) logarithms logP_{i}(X) with degP_{i} ≤ ⌈1/2 degP⌉ and of log h_{1}(X).

2. The algorithm returns the logarithm of h_{1}(X) and the logarithms of all the elements of K of the form X + a, for a in F_{q2}.

Let P(X) be an element of K for which we want to compute the discrete logarithm. Here P is a polynomial of degree at most k − 1 and with coefficients in F_{q2}. We start by applying the algorithm of the above Proposition to P. We obtain a relation of the form

log P = e_{0} log h_{1} + e_{i} log P_{i},

where the sum has at most κq^{2}k terms for a constant κ and the P_{i}’s have degree at most ⌈1/2 degP⌉. Then, we apply recursively the algorithm to the P_{i}’s, thus creating a descent procedure where at each step, a given element P is expressed as a product of elements, whose degree is at most half the degree of P (rounded up) and the arity of the descent tree is in O(q^{2}k). At the end of the process, the logarithm of P is expressed as a linear combination of the logarithms of h_{1} and of the linear polynomials, for which the logarithms are computed with the algorithm in the above Proposition in its second form.

We are left with the complexity analysis of the descent process. Each internal node of the descent tree corresponds to one application of the algorithm of the above Proposition, therefore each internal node has a cost which is bounded by a polynomial in q and k. The total cost of the descent is therefore bounded by the number of nodes in the descent tree times a polynomial in q and k. The depth of the descent tree is in O(log k). The number of nodes of the tree is then less than or equal to its arity raised to the power of its depth, which is (q^{2}k)^{O(log k)}. Since any polynomial in q and k is absorbed in the O() notation in the exponent, we obtain the following result.

Let K = F_{q2}k be a finite field that admits a sparse medium subfield representation. Assuming the same heuristics as in the above Proposition, any discrete logarithm in K can be computed in a time bounded by

max(q, k)^{O(log k)}