Finite fields

Finite fields are provided in Nemo by Flint. This allows construction of finite fields of any characteristic and degree for which there are Conway polynomials. It is also possible for the user to specify their own irreducible polynomial generating a finite field.

Finite fields are constructed using the FlintFiniteField function. However, for convenience we define

FiniteField = FlintFiniteField

so that finite fields can be constructed using FiniteField rather than FlintFiniteField. Note that this is the name of the constructor, but not of finite field type.

The types of finite field elements in Nemo are given in the following table, along with the libraries that provide them and the associated types of the parent objects.

Library	Field	Element type	Parent type
Flint	$\mathbb{F}_{p^n}$ (small $p$)	`fqPolyRepFieldElem`	`fqPolyRepField`
Flint	$\mathbb{F}_{p^n}$ (large $p$)	`FqPolyRepFieldElem`	`FqPolyRepField`

The only difference between the FqPolyRepFieldElem and fqPolyRepFieldElem types is the representation. The former is for finite fields with multiprecision characteristic and the latter is for characteristics that fit into a single unsigned machine word. The FlintFiniteField constructor automatically picks the correct representation for the user, and so the average user doesn't need to know about the actual types.

All the finite field types belong to the FinField abstract type and the finite field element types belong to the FinFieldElem abstract type.

Since all the functionality for the FqPolyRepFieldElem finite field type is identical to that provided for the fqPolyRepFieldElem finite field type, we simply document the former.

Finite field functionality

Finite fields in Nemo provide all the field functionality described in AbstractAlgebra:

https://nemocas.github.io/AbstractAlgebra.jl/stable/field

Below we describe the functionality that is provided in addition to this.

Constructors

In order to construct finite field elements in Nemo, one must first construct the finite field itself. This is accomplished with one of the following constructors.

FlintFiniteField — Function

FlintFiniteField(char::ZZRingElem, deg::Int, s::VarName; cached = true)

Returns a tuple $S, x$ consisting of a finite field parent object $S$ and generator $x$ for the finite field of the given characteristic and degree. The string $s$ is used to designate how the finite field generator will be printed. The characteristic must be prime. When a Conway polynomial is known, the field is generated using the Conway polynomial. Otherwise a random sparse, irreducible polynomial is used. The generator of the field is guaranteed to be a multiplicative generator only if the field is generated by a Conway polynomial. We require the degree to be positive.

FlintFiniteField(pol::Union{ZZModPolyRingElem, FpPolyRingElem}, s::VarName; cached = true, check = true)

Returns a tuple $S, x$ consisting of a finite field parent object $S$ and generator $x$ for the finite field over $F_p$ defined by the given polynomial, i.e. $\mathbb{F}_p[t]/(pol)$. The characteristic is specified by the modulus of pol. The polynomial is required to be irreducible, but this is not checked. The base ring of the polynomial is required to be a field, which is checked by default. Use check = false to disable the check. The string $s$ is used to designate how the finite field generator will be printed. The generator will not be multiplicative in general.

FlintFiniteField(F::FqPolyRepField, deg::Int, s::VarName; cached = true)

Return a finite field with the same type as F but with a possibly different degree deg over the prime subfield.

Here are some examples of creating finite fields and making use of the resulting parent objects to coerce various elements into those fields.

Examples

julia> R, x = FiniteField(7, 3, "x")
(Finite field of degree 3 over GF(7), x)

julia> S, y = FiniteField(ZZ(12431351431561), 2, "y")
(Finite field of degree 2 over GF(12431351431561), y)

julia> T, t = polynomial_ring(residue_ring(ZZ, 12431351431561), "t")
(Univariate polynomial ring in t over ZZ/(12431351431561), t)

julia> U, z = FiniteField(t^2 + 7, "z")
(Finite field of degree 2 over GF(12431351431561), z)

julia> a = R(5)
5

julia> b = R(x)
x

julia> c = S(ZZ(11))
11

julia> d = U(7)
7

Basic manipulation

gen — Method

gen(a::FqPolyRepField)

Return the generator of the finite field. Note that this is only guaranteed to be a multiplicative generator if the finite field is generated by a Conway polynomial automatically.

is_gen — Method

is_gen(a::FqPolyRepFieldElem)

Return true if the given finite field element is the generator of the finite field, otherwise return false.

coeff — Method

coeff(x::FqPolyRepFieldElem, n::Int)

Return the degree $n$ coefficient of the polynomial representing the given finite field element.

degree — Method

degree(a::FqPolyRepField)

Return the degree of the given finite field.

modulus — Method

modulus(k::FqPolyRepField, var::VarName=:T)

Return the modulus defining the finite field $k$.

Examples

julia> R, x = FiniteField(ZZ(7), 5, "x")
(Finite field of degree 5 over GF(7), x)

julia> c = gen(R)
x

julia> d = characteristic(R)
7

julia> f = order(R)
16807

julia> g = degree(R)
5

julia> n = is_gen(x)
true

Special functions

Various special functions with finite field specific behaviour are defined.

tr — Method

tr(x::FqPolyRepFieldElem)

Return the trace of $x$. This is an element of $\mathbb{F}_p$, but the value returned is this value embedded in the original finite field.

norm — Method

norm(x::FqPolyRepFieldElem)

Return the norm of $x$. This is an element of $\mathbb{F}_p$, but the value returned is this value embedded in the original finite field.

frobenius — Method

frobenius(x::FqPolyRepFieldElem, n = 1)

Return the iterated Frobenius $\sigma_p^n(x)$ where $\sigma_p$ is the Frobenius map sending the element $a$ to $a^p$ in the finite field of characteristic $p$. By default the Frobenius map is applied $n = 1$ times if $n$ is not specified.

pth_root — Method

pth_root(x::FqPolyRepFieldElem)

Return the $p$-th root of $x$ in the finite field of characteristic $p$. This is the inverse operation to the Frobenius map $\sigma_p$.

Examples

julia> R, x = FiniteField(ZZ(7), 5, "x")
(Finite field of degree 5 over GF(7), x)

julia> a = x^4 + 3x^2 + 6x + 1
x^4 + 3*x^2 + 6*x + 1

julia> b = tr(a)
1

julia> c = norm(a)
4

julia> d = frobenius(a)
x^4 + 2*x^3 + 3*x^2 + 5*x + 1

julia> f = frobenius(a, 3)
3*x^4 + 3*x^3 + 3*x^2 + x + 4

julia> g = pth_root(a)
4*x^4 + 3*x^3 + 4*x^2 + 5*x + 2

Lift

lift — Method

lift(R::FpPolyRing, x::FqPolyRepFieldElem)

Lift the finite field element x to a polynomial over the prime field.

Examples

julia> R, x = FiniteField(23, 2, "x")
(Finite field of degree 2 over GF(23), x)

julia> S, y = polynomial_ring(GF(23), "y")
(Univariate polynomial ring in y over GF(23), y)

julia> f = 8x + 9
8*x + 9

julia> lift(S, f)
8*y + 9

Uniform finite fields

An (experimental) uniform finite field interface is provided by the type FqField. Such a finite field can be constructed as an extension of a prime field $\mathbf{F}_p$ (an absolute extension) or of another finite field (a relative extension). The field over which the extension is constructed is referred to as the base field and field theoretic properties like the degree of an extension or the trace of an element are understood with respect to the base field. The corresponding functionality for the implicit absolute extension over the prime field is available by methods with the prefix absolute_.

Note that all finite fields are simple extension $k[t]/(f)$ of their base field $k$. The irreducible polynomial $f \in k[t]$ is the defining polynomial and the class of $t$ is referred to as the generator of the extension.

Construction of finite fields

_FiniteField — Function

_FiniteField(q::IntegerUnion, s::String; cached::Bool, check::Bool)
_FiniteField(p::IntegerUnion, d::Int, s::String; cached::Bool, check::Bool)
_FiniteField(f::FqPolyRingElem; s::String; cached::Bool, check::Bool)

Returns a tuple $S, x$ consisting of a finite field $S$ of order $q = p^e$ and algebra generator $x$. The string $s$ is used to designate how the finite field generator will be printed.

If a polynomial $f \in k[t]$ over a finite field $k$ is specified, the finite field $S = k[t]/(f)$ will be constructed as a finite field with base field $k$.

_GF — Function

_GF(q::IntegerUnion, s::String; cached::Bool, check::Bool)
_GF(p::IntegerUnion, d::Int, s::String; cached::Bool, check::Bool)
_GF(f::FqPolyRingElem; s::String; cached::Bool, check::Bool)

Returns a tuple $S$ consisting of a finite field $S$ of order $q = p^e$ and algebra generator $x$. The string $s$ is used to designate how the finite field generator will be printed.

If a polynomial $f \in k[t]$ over a finite field $k$ is specified, the finite field $S = k[t]/(f)$ will be constructed as a finite field with base field $k$.

Field properties

base_field — Method

base_field(F::FqField)

Return the base field of F.

prime_field — Method

prime_field(F::FqField)

Return the prime field of F.

degree — Method

degree(a::FqField)

Return the degree of the given finite field over the base field.

absolute_degree — Method

absolute_degree(a::FqField)

Return the degree of the given finite field over the prime field.

is_absolute — Method

is_absolute(F::FqField)

Return whether the base field of $F$ is a prime field.

defining_polynomial — Method

defining_polynomial([R::FqPolyRing], L::FqField)

Return the defining polynomial of L as a polynomial over the base field of L.

If the polynomial ring R is specified, the polynomial will be an element of R.

Element properties

tr — Method

tr(x::FqFieldElem)

Return the trace of $x$. This is an element of the base field.

absolute_tr — Method

absolute_tr(x::FqFieldElem)

Return the absolute trace of $x$. This is an element of the prime field.

norm — Method

norm(x::FqFieldElem)

Return the norm of $x$. This is an element of the base field.

absolute_norm — Method

absolute_norm(x::FqFieldElem)

Return the absolute norm of $x$. This is an element of the prime field.