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 = FlintFiniteFieldso 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$) | fq_nmod | FqNmodFiniteField |
| Flint | $\mathbb{F}_{p^n}$ (large $p$) | fq | FqFiniteField |
The only difference between the fq and fq_nmod 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 fq finite field type is identical to that provided for the fq_nmod finite field type, we simply document the former.
Finite field functionality
Finite fields in Nemo implement the entire AbstractAlgebra.jl field interface.
https://nemocas.github.io/AbstractAlgebra.jl/fields.html
Below we describe the functionality that is provided in addition to this interface.
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.
Nemo.FlintFiniteField — Method.FlintFiniteField(char::fmpz, deg::Int, s::AbstractString; 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.
Nemo.FlintFiniteField — Method.FlintFiniteField(char::Integer, deg::Int, s::AbstractString; 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(::fmpz_mod_poly, ::AbstractString)
FlintFiniteField(::gfp_fmpz_poly, ::AbstractString)Here are some examples of creating finite fields and making use of the resulting parent objects to coerce various elements into those fields.
Examples
R, x = FiniteField(7, 3, "x")
S, y = FiniteField(ZZ(12431351431561), 2, "y")
T, t = PolynomialRing(ResidueRing(ZZ, 12431351431561), "t")
U, z = FiniteField(t^2 + 7, "z")
a = R(5)
b = R(x)
c = S(ZZ(11))
d = U(7)Basic manipulation
AbstractAlgebra.Generic.gen — Method.gen(a::FqFiniteField)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.
AbstractAlgebra.Generic.isgen — Method.isgen(a::fq)Return
trueif the given finite field element is the generator of the finite field, otherwise returnfalse.
AbstractAlgebra.Generic.coeff — Method.coeff(x::fq, n::Int)Return the degree $n$ coefficient of the polynomial representing the given finite field element.
AbstractAlgebra.Generic.degree — Method.degree(a::FqFiniteField)Return the degree of the given finite field.
AbstractAlgebra.Generic.characteristic — Method.characteristic(a::FqFiniteField)Return the characteristic of the given finite field.
AbstractAlgebra.Generic.order — Method.order(a::FqFiniteField)Return the order, i.e. the number of elements in, the given finite field.
Examples
R, x = FiniteField(ZZ(7), 5, "x")
c = gen(R)
d = characteristic(R)
f = order(R)
g = degree(R)
n = isgen(x)Special functions
Various special functions with finite field specific behaviour are defined.
LinearAlgebra.tr — Method.tr(x::fq)Return the trace of $a$. This is an element of $\F_p$, but the value returned is this value embedded in the original finite field.
LinearAlgebra.norm — Method.norm(x::fq)Return the norm of $a$. This is an element of $\F_p$, but the value returned is this value embedded in the original finite field.
Nemo.frobenius — Method.frobenius(x::fq, n = 1)Return the iterated Frobenius $\sigma_p^n(a)$ 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.
Nemo.pth_root — Method.pth_root(x::fq)Return the $p$-th root of $a$ in the finite field of characteristic $p$. This is the inverse operation to the Frobenius map $\sigma_p$.
Examples
R, x = FiniteField(ZZ(7), 5, "x")
a = x^4 + 3x^2 + 6x + 1
b = tr(a)
c = norm(a)
d = frobenius(a)
f = frobenius(a, 3)
g = pth_root(a)