A finite field K admits a sparse medium subfield representation if
– it has a subfield of q2 elements for a prime power q, i.e. K is isomorphic to Fq2k with k ≥ 1;
– there exist two polynomials h0 and h1 over Fq2 of small degree, such that h1Xq − h0 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 h0 and h1 are uniformly bounded by a constant δ. Any finite field of the form Fq2k with k ≤ q + 2 admits a sparse medium subfield representation with polynomials h0 and h1 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 Fq2. 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 = Fq2k 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 ∈ Fq2[X] with 2 ≤ deg P ≤ k − 1, the algorithm returns an expression of log P (X ) as a linear combination of at most O(kq2) logarithms logPi(X) with degPi ≤ ⌈1/2 degP⌉ and of log h1(X).
2. The algorithm returns the logarithm of h1(X) and the logarithms of all the elements of K of the form X + a, for a in Fq2.
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 Fq2. We start by applying the algorithm of the above Proposition to P. We obtain a relation of the form
log P = e0 log h1 + ei log Pi,
where the sum has at most κq2k terms for a constant κ and the Pi’s have degree at most ⌈1/2 degP⌉. Then, we apply recursively the algorithm to the Pi’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(q2k). At the end of the process, the logarithm of P is expressed as a linear combination of the logarithms of h1 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 (q2k)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 = Fq2k 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)