Algorithmic Subfield Representation of the Depth of Descent Tree

A finite field K admits a sparse medium subfield representation if

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

– there exist two polynomials h₀ and h₁ over F_q² of small degree, such that h₁X^q − h₀ 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₀ and h₁ are uniformly bounded by a constant δ. Any finite field of the form F_q^2k with k ≤ q + 2 admits a sparse medium subfield representation with polynomials h₀ and h₁ 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_q². 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_q^2k 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_q²[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²) logarithms logP_i(X) with degP_i ≤ ⌈1/2 degP⌉ and of log h₁(X).

2. The algorithm returns the logarithm of h₁(X) and the logarithms of all the elements of K of the form X + a, for a in F_q².

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_q². We start by applying the algorithm of the above Proposition to P. We obtain a relation of the form

log P = e₀ log h₁ + e_i log P_i,

where the sum has at most κq²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²k). At the end of the process, the logarithm of P is expressed as a linear combination of the logarithms of h₁ 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²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_q²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)}

Advertisement