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.