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.