Frobenius map, norm, trace and roots

The Galois group of \mathbb{F}_q/\mathbb{F}_p, q = p^d, is cyclic of order d, generated by the Frobenius automorphism \sigma(a) = a^p [LN1997]. The trace and the norm are

which lie in \mathbb{F}_p; equivalently they are the trace and the determinant of the \mathbb{F}_p-linear map x \mapsto ax on \mathbb{F}_q. This section describes how the polynomial representations fq and fq_nmod compute them, with \mathbb{F}_q = \mathbb{F}_p[x]/(f) for an irreducible f of degree d with roots \alpha_1, \ldots, \alpha_d (the conjugates of the generator); for the Zech representation see Zech logarithms.

The Frobenius map#

fq_frobenius computes \sigma^e(a) = a^{p^e}, for e reduced to [0, d), by binary exponentiation with exponent p^e (_fq_pow), which costs about e \log_2 p squarings and fewer multiplications. For a \in \mathbb{F}_p (a constant representative) the result is a.

The Frobenius map is \mathbb{F}_p-linear, so a matrix of \sigma^e would make each application cost O(d^2) operations in \mathbb{F}_p after an O(d^3) precomputation, and \sigma^e(a) = a(\xi) \bmod f with \xi = x^{p^e} \bmod f, so it can also be computed by modular composition (Composition and modular composition) [GatSho1992]; FLINT uses these techniques for polynomials over \mathbb{F}_q (the iterated Frobenius x^{q^i} \bmod v of fq_poly_iterated_frobenius_preinv) but not for single elements. The p-th root, the inverse of \sigma, is computed as \sigma^{d-1}(a) = a^{p^{d-1}} by d - 1 successive p-th powers (fq_pth_root). The lift of the Frobenius map to the unramified p-adic extension \mathbf{Q}_q is described in Frobenius automorphism and Teichmüller lifts in unramified extensions.

The trace#

Since the trace is \mathbb{F}_p-linear, \operatorname{Tr}(\sum_i a_i x^i) = \sum_i a_i \operatorname{Tr}(x^i), and the traces of the basis elements are the power sums s_i = \operatorname{Tr}(x^i) = \sum_j \alpha_j^i of the roots of f.

_fq_trace computes s_0, \ldots, s_{d-1} by the recurrence of Lemma 1, using only the nonzero coefficients of the monic version of f, so the cost is O(dt) operations for a polynomial with t nonzero terms, and then the dot product \sum a_i s_i. The same power sums appear in fq_embed_mono_to_dual_matrix, which computes \operatorname{Tr}(x^{i+j}) for all i + j < 2d - 1 from the series expansion of \operatorname{rev}(f')/\operatorname{rev}(f), the reversed form of the series in the proof.

The norm#

_fq_norm computes the resultant with _fmpz_mod_poly_resultant (_nmod_poly_resultant for fq_nmod), which uses the Euclidean or half-GCD algorithm (Half-GCD), and divides by c^m when f is not monic. For a \in \mathbb{F}_p it returns a^d.

Square roots and squares#

The group \mathbb{F}_q^\times is cyclic of order q - 1, so for odd p exactly half of its elements are squares, and a \ne 0 is a square if and only if a^{(q-1)/2} = 1 (Euler's criterion; fq_is_square). In characteristic 2 every element is a square, with the unique square root \sigma^{-1}(a).

The invariant is b^2 = a u, with u in the subgroup of order 2^M and c a generator of the subgroup of order 2^M; each iteration decreases the order of u, so there are at most s iterations of at most s squarings each [Ton1891] [Sha1973]. fq_sqrt takes as z the generator of the field if the context was created from a Conway polynomial, which is primitive and hence not a square, and otherwise draws random elements until it finds a non-square (half of all elements qualify). The cost is O(\log q) multiplications for the three powers and O(s^2) for the loop. fq_poly_sqrt computes square roots of polynomials with a power series square root and fq_sqrt for the lowest nonzero coefficient.

Multiplicative order#

The order of a \ne 0 divides q - 1. fq_multiplicative_order factors q - 1 = \prod \ell_i^{e_i} with fmpz_factor, and for each prime \ell_i divides the candidate order by \ell_i as long as a raised to the result is still 1; this needs O(\sum_i e_i) exponentiations. For large q the factorisation of q - 1 dominates. An element is primitive if and only if its order is q - 1 (fq_is_primitive), and a defining polynomial is primitive if and only if its root fq_gen is.

Use in FLINT#

• fq_frobenius, fq_nmod_frobenius (exponentiation), fq_zech_frobenius (multiplication of the logarithm by p^e), and fq_default_frobenius.
• fq_trace, fq_nmod_trace (Lemma 1); fq_zech_trace (sum of the conjugates).
• fq_norm, fq_nmod_norm (Proposition 2); fq_zech_norm (a power of the norm of the generator).
• fq_pth_root, fq_nmod_pth_root, fq_sqrt, fq_nmod_sqrt (Algorithm 1), fq_is_square, fq_multiplicative_order and the corresponding fq_nmod and fq_default functions; fq_zech computes square roots and p-th roots on logarithms.