GitHub

Finite fields

A finite field $K$ is represented as simple extension $K = k(\alpha) = k[x]/(f)$, where $k$ can be

  • a prime field $\mathbf{F}_p$ ($K$ is then an absolute finite field), or
  • an arbitrary finite field $k$ ($K$ is then a relative finite field).

In both cases, we call $k$ the base field of $K$, $\alpha$ a generator and $f$ the defining polynomial of $K$.

Note that all field theoretic properties (like basis, degree or trace) are defined with respect to the base field. Methods with prefix absolute_ return

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

finite_field — Function
finite_field(p::IntegerUnion, d::Int, s::VarName = :o; cached::Bool = true, check::Bool = true)
finite_field(q::IntegerUnion, s::VarName = :o; cached::Bool = true, check::Bool = true)
finite_field(f::FqPolyRingElem, s::VarName = :o; cached::Bool = true, check::Bool = true)

Return a tuple $(K, x)$ of a finite field $K$ of order $q = p^d$, where $p$ is a prime, and a generator $x$ of $K$ (see gen for a definition). The identifier $s$ is used to designate how the finite field generator will be printed.

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

See also GF which only returns $K$.

Examples

julia> K, a = finite_field(3, 2, "a")
(Finite field of degree 2 and characteristic 3, a)

julia> K, a = finite_field(9, "a")
(Finite field of degree 2 and characteristic 3, a)

julia> Kx, x = K["x"];

julia> L, b = finite_field(x^3 + x^2 + x + 2, "b")
(Finite field of degree 3 over GF(3, 2), b)
source
GF — Function
GF(p::IntegerUnion, d::Int, s::VarName = :o; cached::Bool = true, check::Bool = true)
GF(q::IntegerUnion, s::VarName = :o; cached::Bool = true, check::Bool = true)
GF(f::FqPolyRingElem, s::VarName = :o; cached::Bool = true, check::Bool = true)

Return a finite field $K$ of order $q = p^d$, where $p$ is a prime. The identifier $s$ is used to designate how the finite field generator will be printed.

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

See also finite_field which additionally returns a finite field generator of $K$.

Examples

julia> K = GF(3, 2, "a")
Finite field of degree 2 and characteristic 3

julia> K = GF(9, "a")
Finite field of degree 2 and characteristic 3

julia> Kx, x = K["x"];

julia> L = GF(x^3 + x^2 + x + 2, "b")
Finite field of degree 3 over GF(3, 2)
source

Field functionality

degree — Method
degree(K::FqField) -> Int

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

Examples

julia> K, a = finite_field(3, 2, "a");

julia> degree(K)
2

julia> Kx, x = K["x"];

julia> L, b = finite_field(x^3 + x^2 + x + 2, "b");

julia> degree(L)
3
source
absolute_degree — Method
absolute_degree(a::FqField)

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

source
is_absolute — Method
is_absolute(F::FqField)

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

source
defining_polynomial — Method
defining_polynomial([R::FqPolyRing], K::FqField)

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

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

Examples

julia> K, a = finite_field(9, "a");

julia> defining_polynomial(K)
x^2 + 2*x + 2

julia> Ky, y = K["y"];

julia> L, b = finite_field(y^3 + y^2 + y + 2, "b");

julia> defining_polynomial(L)
y^3 + y^2 + y + 2
source

Element functionality

gen — Method
gen(L::FqField)

Return a $K$-algebra generator a of the finite field $L$, where $K$ is the base field of $L$. The element a satisfies defining_polyomial(a) == 0.

Note that this is in general not a multiplicative generator and can be zero, if $L/K$ is an extension of degree one.

source
is_gen — Method
is_gen(a::FqFieldElem)

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

source
tr — Method
tr(x::FqFieldElem)

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

source
absolute_tr — Method
absolute_tr(x::FqFieldElem)

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

source
norm — Method
norm(x::FqFieldElem)

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

source
absolute_norm — Method
absolute_norm(x::FqFieldElem)

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

source
lift — Method
lift(R::FqPolyRing, a::FqFieldElem) -> FqPolyRingElem

Given a polynomial ring over the base field of the parent of a, return a lift such that parent(a)(lift(R, a)) == a is true.

source
lift — Method
lift(::ZZRing, x::FqFieldElem) -> ZZRingElem

Given an element $x$ of a prime field $\mathbf{F}_p$, return a preimage under the canonical map $\mathbf{Z} \to \mathbf{F}_p$.

Examples

julia> K = GF(19);

julia> lift(ZZ, K(3))
3
source