Structure Operations

Related Structures

Category(F): FldFin -> Cat

Parent(F): FldFin -> PowerStructure

Centre(F): FldFin -> FldFin

PrimeRing(F): FldFin -> FldFin

PrimeField(F): FldFin -> FldFin

FieldOfFractions(F): FldFin -> FldFin

AdditiveGroup(F): FldFin -> GrpAb, Map

Given \(F={\bf F}_{q}\), create the finite additive abelian group \(A\) of order \(q=p^r\) that is the direct sum of \(r\) copies of the cyclic group of order \(p\), together with the corresponding isomorphism from the group \(A\) to the field \(F\).

MultiplicativeGroup(F): FldFin -> GrpAb, Map

UnitGroup(F): FldFin -> GrpAb, Map

Given \(F={\bf F}_{q}\), create the multiplicative group of \(R\) as an abelian group. This returns the (additive) cyclic group \(A\) of order \(q-1\), together with a map from \(A\) to \(F\setminus 0\), sending \(1\) to a primitive element of \(F\).

Set(F): FldFin -> SetEnum

Create the enumerated set consisting of the elements of finite field \(F\).

VectorSpace(F, E): FldFin, FldFin -> ModTupFld, Map

Given a finite field \(F\) that is an extension of degree \(n\) of \(E\), define the natural isomorphism between \(F\) and the \(n\)-dimensional vector space \(E^n\). The function returns two values:

(a)

A vector space \(V\cong E^n\);

(b)

The isomorphism \(\phi : F \rightarrow V\).

The basis of \(V\) is chosen to correspond with the power basis \(\alpha^0\), \(\alpha^1\), \(\ldots\), \(\alpha^{n-1}\) of \(F\), where \(\alpha\) is the generator returned by Generator(F, E), so that \(V=E\cdot1\times E\cdot\alpha\times\cdots\times E\cdot\alpha^{n-1}\) and \(\phi : \alpha^i \rightarrow e_{i+1}\), (for \(i = 0, \ldots, n-1\)), where \(e_i\) is the basis vector of \(V\) having all components zero, except the \(i\)-th, which is one.

VectorSpace(F, E, B): FldFin, FldFin, [ FldFinElt ] -> ModTupFld, Map

Given a finite field \(F\) that is an extension of degree \(n\) of \(E\), define the isomorphism between \(F\) and the \(n\)-dimensional vector space \(E^n\) defined by the basis \(B\) for \(F\) over \(E\). The function returns two values:

(a)

A vector space \(V\cong E^n\);

(b)

The isomorphism \(\phi : F \rightarrow V\).

The basis of \(V\) is chosen to correspond with the basis \(B=\beta_1, \beta_2, \ldots, \beta_{n}\) of \(F\) over \(E\), as specified by the user, so that \(V=E\cdot\beta_1\times E\cdot\beta_2\times\cdots\times E\cdot\beta_{n}\). \(\phi : \beta_i \rightarrow e_{i}\), (for \(i = 1, \ldots, n\)), where \(e_i\) is the basis vector of \(V\) having all components zero, except the \(i\)-th, which is one.

MatrixAlgebra(F, E): FldFin, FldFin -> AlgMat, Map

Let \(F\) be a finite field that is an extension of degree \(n\) of \(E\). The function returns two values:

(a)

A matrix algebra \(A\) of degree \(n\), such that \(A\) is isomorphic to \(F\);

(b)

An isomorphism \(\phi : F \rightarrow A\).

The matrix algebra \(A\) will be the subalgebra of the full algebra of \(n\times n\) matrices over \(E\) generated by the companion matrix \(C\) of the defining polynomial of \(F\) over \(E\). The generator Generator(F, E) of \(F\) over \(E\) is thus mapped to \(C\).

MatrixAlgebra(A, E): AlgMat, FldFin -> AlgMat, Map

Let \(F\) be a finite field. Let \(A\) be a matrix algebra over \(F\), and \(E\) be a subfield of \(F\). The function returns two values:

(a)

A matrix algebra \(N\) over \(E\) isomorphic to \(A\), obtained from \(A\) by expanding each component of an element of \(A\) into the block matrix associated with it;

(b)

An \(E\)-isomorphism \(\phi : A \rightarrow N\).

The matrix algebra \(N\) is \(A\) considered as an \(E\)-matrix algebra.

Example: Finite Field as a Vector Space (ex-c6682e)

Given the field \(F\) of \(7^4\) elements defined as an extension of the field \(F49\) of \(7^2\) elements as above, we can construct two vector spaces, one of dimension 2, and the other of dimension 4:

> F7 := FiniteField(7);
> F49<w> := ext< F7 | 2 >;
> F<z> := ext< F49 | 2 >;
> v2, i2 := VectorSpace(F, F49);
> v2;
Full Vector space of degree 2 over GF(7^2)
> i2(z^12);
(   w w^28)
> v4, i4 := VectorSpace(F, PrimeField(F));
> v4;
Full Vector space of degree 4 over GF(7)
> i4(z^12);
(5 3 6 4)

Run in calculator (opens in a new tab)Copy input

GaloisGroup(K, k): FldFin, FldFin -> GrpPerm, [FldFinElt]

Compute the Galois group (which is of course cyclic) of \(K/k\) as a permutation group. The group is returned as well as the roots of the defining polynomial of \(K/k\) in a compatible ordering.

AutomorphismGroup(K, k): FldFin, FldFin -> GrpPerm, [Map], Map

Computes the (cyclic) group of \(k\)-automorphisms of \(K\). The group is returned as well as a sequence of all automorphisms and a map sending an element of the abstract automorphism group to an explicit automorphism.

Numerical Invariants

Characteristic(F): FldFin -> RngIntElt

# F: FldFin -> FldFinElt

Degree(F): FldFin -> RngIntElt

The absolute degree of \(F\), that is, the degree over its prime subfield.

Degree(F, E): FldFin, FldFin -> RngIntElt

Given a finite field \(F\) that has been constructed as an extension of a field \(E\), return the degree of \(F\) over \(E\).

Defining Polynomial

DefiningPolynomial(F): FldFin -> RngUPolElt

Given a finite field \(F\) that has been constructed as an extension of a field \(E\), return the polynomial with coefficients in \(E\) that was used to define \(F\) as an extension of \(E\). This is the minimum polynomial of F.1.

DefiningPolynomial(F, E): FldFin -> RngUPolElt

Given a finite field \(F\) and a subfield \(E\), return the polynomial with coefficients in \(E\) used to define \(F\) as an extension of \(E\). This is the same as the minimum polynomial of the generator Generator(F, E) over \(E\).

Ring Predicates and Booleans

IsConway(F): FldFin -> BoolElt

Given a finite field \(F\), this function returns true iff \(F\) is defined over its prime field using a Conway polynomial.

IsDefault(F): FldFin -> BoolElt

Given a finite field \(F\), this function returns true iff \(F\) is a default field.

IsCommutative(F): FldFin -> BoolElt

IsUnitary(F): FldFin -> BoolElt

IsFinite(F): FldFin -> BoolElt

IsOrdered(F): FldFin -> BoolElt

IsField(F): FldFin -> BoolElt

IsEuclideanDomain(F): FldFin -> BoolElt

IsPID(F): FldFin -> BoolElt

IsUFD(F): FldFin -> BoolElt

IsDivisionRing(F): FldFin -> BoolElt

IsEuclideanRing(F): FldFin -> BoolElt

IsPrincipalIdealRing(F): FldFin -> BoolElt

IsDomain(F): FldFin -> BoolElt

F eq G: FldFin, Rng -> BoolElt

F ne G: FldFin, Rng -> BoolElt

Roots

Roots(f): RngUPolElt -> [ < FldFinElt, RngIntElt> ]

Given a polynomial \(f\) over a finite field \(F\), this function finds all roots of \(f\) in \(F\), and returns a sorted sequence of tuples (pairs), each consisting of a root of \(f\) in \(F\) and its multiplicity.

RootsInSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin

Given a univariate polynomial \(f\) over a finite field \(K\), compute the minimal splitting field \(S\) of \(f\) as an extension field of \(K\), and return the roots of \(f\) in \(S\), together with \(S\). Using this function will be faster than computing the roots of \(f\) anew over the splitting field.

FactorizationOverSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin

FactorisationOverSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin

Given a univariate polynomial \(f\) over a finite field \(K\), compute the minimal splitting field \(S\) of \(f\) as an extension field of \(K\), and return the factorization (into linears) of \(f\) over \(S\), together with \(S\). Using this function will be faster than factorizing \(f\) anew over the splitting field.

RootOfUnity(n, K): RngIntElt, FldFin -> FldFinElt

Return a primitive \(n\)-th root of unity in the smallest possible extension field of \(K\).

Example: Roots in a Splitting Field (ex-f06af7)

Run in calculator (opens in a new tab)Copy input

We compute the roots of a certain degree-20 polynomial \(f\) in its minimal splitting field.

> K := GF(2);
> P<x> := PolynomialRing(GF(2));
> f := x^20 + x^11 + 1;
> Factorization(f);
[
    <x^3 + x^2 + 1, 1>,
    <x^8 + x^7 + x^3 + x^2 + 1, 1>,
    <x^9 + x^7 + x^6 + x^4 + 1, 1>
]
> time r, S<w> := RootsInSplittingField(f);
Time: 0.040

We note that the splitting field \(S\) has degree 72 and there are 20 roots of \(f\) in \(S\) of course. We check that the evaluation of \(f\) at each root is zero.

> S;
Finite field of size 2^72
> DefiningPolynomial(S);
x^72 + x^48 + x^47 + x^44 + x^38 + x^35 + x^32 + x^31 + x^30 +
    x^29 + x^27 + x^25 + x^23 + x^22 + x^21 + x^18 + x^15 +
    x^12 + x^8 + x^4 + 1
> #r;
20
> r[1];
<w^68 + w^67 + w^64 + w^62 + w^60 + w^59 + w^56 + w^50 + w^49 +
    w^48 + w^47 + w^44 + w^43 + w^39 + w^37 + w^35 + w^33 + w^32
    + w^30 + w^29 + w^28 + w^25 + w^21 + w^19 + w^18 + w^16 +
    w^15 + w^14 + w^12 + w^10 + w^6 + w, 1>
> [IsZero(Evaluate(f, t[1])): t in r];
[ true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true ]

Run in calculator (opens in a new tab)Copy input