Frobenius map, norm and trace

The Galois group of $\mathbb{F}_q/\mathbb{F}_p$, $q = p^d$, is cyclic of order $d$ and generated by the Frobenius automorphism $\sigma(a) = a^p$. fq_frobenius applies its powers, and fq_norm and fq_trace compute the product and the sum of the $d$ conjugates $\sigma^i(a)$, which are elements of the prime field, returned as integers in $[0, p)$. The same functions exist for fq_nmod, fq_zech and fq_default; the algorithms, Newton's identities for the trace and a resultant for the norm, are described in Frobenius map, norm, trace and roots.

Example#

The program works in $\mathbb{F}_{7^5}$, defined by the Conway polynomial $f = X^5 + X + 4$, and compares the norm and the trace of $a = x + 2$ with the product and the sum of its conjugates. Here $N(a) = (-1)^5 f(-2) = 30 \equiv 2$ and, since the power sum $\operatorname{Tr}(x)$ is minus the coefficient of $X^4$, $\operatorname{Tr}(a) = 0 + 5 \cdot 2 \equiv 3$. It also checks that $\sigma^5$ is the identity and that $\sigma^{-1}$, which fq_frobenius accepts as the exponent $-1 \equiv 4 \pmod 5$, is the $p$-th root.

#include <flint/flint.h>
#include <flint/fmpz.h>
#include <flint/fq.h>

int main(void)
{
    fmpz_t p, n, t;
    fq_ctx_t ctx;
    fq_t a, c, prod, sum;
    slong i, d = 5;

    fmpz_init_set_ui(p, 7);
    fmpz_init(n);
    fmpz_init(t);
    fq_ctx_init(ctx, p, d, "x");                  /* GF(7^5) */
    fq_init(a, ctx);
    fq_init(c, ctx);
    fq_init(prod, ctx);
    fq_init(sum, ctx);

    fq_ctx_print(ctx);
    fq_gen(a, ctx);
    fq_set_ui(c, 2, ctx);
    fq_add(a, a, c, ctx);                         /* a = x + 2 */

    fq_one(prod, ctx);
    fq_zero(sum, ctx);
    for (i = 0; i < d; i++)
    {
        fq_frobenius(c, a, i, ctx);               /* c = a^(7^i) */
        fq_mul(prod, prod, c, ctx);
        fq_add(sum, sum, c, ctx);
    }

    fq_norm(n, a, ctx);
    fq_trace(t, a, ctx);
    flint_printf("norm  = %{fmpz}, product of conjugates = ", n);
    fq_print_pretty(prod, ctx);
    flint_printf("\ntrace = %{fmpz}, sum of conjugates = ", t);
    fq_print_pretty(sum, ctx);
    flint_printf("\n");

    fq_frobenius(c, a, d, ctx);
    flint_printf("sigma^5(a) == a: %d\n", fq_equal(c, a, ctx));
    fq_frobenius(c, a, -1, ctx);
    fq_pth_root(prod, a, ctx);
    flint_printf("sigma^-1(a) == pth_root(a): %d\n", fq_equal(c, prod, ctx));

    fq_clear(a, ctx);
    fq_clear(c, ctx);
    fq_clear(prod, ctx);
    fq_clear(sum, ctx);
    fq_ctx_clear(ctx);
    fmpz_clear(p);
    fmpz_clear(n);
    fmpz_clear(t);
    return 0;
}

p = 7
d = 5
f(X) = X^5+X+4
norm  = 2, product of conjugates = 2
trace = 3, sum of conjugates = 3
sigma^5(a) == a: 1
sigma^-1(a) == pth_root(a): 1

Costs#

fq_frobenius computes $a^{p^e}$ by binary exponentiation, about $e \log_2 p$ squarings; for repeated applications of the same power to many elements, the matrix of $\sigma^e$ (an $\mathbb{F}_p$-linear map, see fq_embed_composition_matrix applied to $x^{p^e}$) can be cheaper. The trace costs $O(dt)$ operations in $\mathbb{F}_p$ for a defining polynomial with $t$ nonzero terms, and the norm one resultant of two polynomials of degree at most $d$.