---
title: "Structure Operations"
canonical: "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/operation.html"
source: "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/operation.md"
part: "Basic Rings"
chapter: "Finite Fields"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Basic Rings", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/index-basic-rings.md"}
  - {"title": "Finite Fields", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/index-finite-fields.md"}
prev: {"title": "Creation Functions", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/creation.md"}
next: {"title": "Element Operations", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/operation-element.md"}
intrinsics:
  - {"name": "Category", "signature": "Category(F): FldFin -> Cat"}
  - {"name": "Parent", "signature": "Parent(F): FldFin -> PowerStructure"}
  - {"name": "Centre", "signature": "Centre(F): FldFin -> FldFin"}
  - {"name": "PrimeRing", "signature": "PrimeRing(F): FldFin -> FldFin"}
  - {"name": "PrimeField", "signature": "PrimeField(F): FldFin -> FldFin"}
  - {"name": "FieldOfFractions", "signature": "FieldOfFractions(F): FldFin -> FldFin"}
  - {"name": "AdditiveGroup", "signature": "AdditiveGroup(F): FldFin -> GrpAb, Map"}
  - {"name": "MultiplicativeGroup", "signature": "MultiplicativeGroup(F): FldFin -> GrpAb, Map"}
  - {"name": "UnitGroup", "signature": "UnitGroup(F): FldFin -> GrpAb, Map"}
  - {"name": "Set", "signature": "Set(F): FldFin -> SetEnum"}
  - {"name": "VectorSpace", "signature": "VectorSpace(F, E): FldFin, FldFin -> ModTupFld, Map"}
  - {"name": "VectorSpace", "signature": "VectorSpace(F, E, B): FldFin, FldFin, [ FldFinElt ] -> ModTupFld, Map"}
  - {"name": "MatrixAlgebra", "signature": "MatrixAlgebra(F, E): FldFin, FldFin -> AlgMat, Map"}
  - {"name": "MatrixAlgebra", "signature": "MatrixAlgebra(A, E): AlgMat, FldFin -> AlgMat, Map"}
  - {"name": "GaloisGroup", "signature": "GaloisGroup(K, k): FldFin, FldFin -> GrpPerm, [FldFinElt]"}
  - {"name": "AutomorphismGroup", "signature": "AutomorphismGroup(K, k): FldFin, FldFin -> GrpPerm, [Map], Map"}
  - {"name": "Characteristic", "signature": "Characteristic(F): FldFin -> RngIntElt"}
  - {"name": "#", "signature": "# F: FldFin -> FldFinElt"}
  - {"name": "Degree", "signature": "Degree(F): FldFin -> RngIntElt"}
  - {"name": "Degree", "signature": "Degree(F, E): FldFin, FldFin -> RngIntElt"}
  - {"name": "DefiningPolynomial", "signature": "DefiningPolynomial(F): FldFin -> RngUPolElt"}
  - {"name": "DefiningPolynomial", "signature": "DefiningPolynomial(F, E): FldFin -> RngUPolElt"}
  - {"name": "IsConway", "signature": "IsConway(F): FldFin -> BoolElt"}
  - {"name": "IsDefault", "signature": "IsDefault(F): FldFin -> BoolElt"}
  - {"name": "IsCommutative", "signature": "IsCommutative(F): FldFin -> BoolElt"}
  - {"name": "IsUnitary", "signature": "IsUnitary(F): FldFin -> BoolElt"}
  - {"name": "IsFinite", "signature": "IsFinite(F): FldFin -> BoolElt"}
  - {"name": "IsOrdered", "signature": "IsOrdered(F): FldFin -> BoolElt"}
  - {"name": "IsField", "signature": "IsField(F): FldFin -> BoolElt"}
  - {"name": "IsEuclideanDomain", "signature": "IsEuclideanDomain(F): FldFin -> BoolElt"}
  - {"name": "IsPID", "signature": "IsPID(F): FldFin -> BoolElt"}
  - {"name": "IsUFD", "signature": "IsUFD(F): FldFin -> BoolElt"}
  - {"name": "IsDivisionRing", "signature": "IsDivisionRing(F): FldFin -> BoolElt"}
  - {"name": "IsEuclideanRing", "signature": "IsEuclideanRing(F): FldFin -> BoolElt"}
  - {"name": "IsPrincipalIdealRing", "signature": "IsPrincipalIdealRing(F): FldFin -> BoolElt"}
  - {"name": "IsDomain", "signature": "IsDomain(F): FldFin -> BoolElt"}
  - {"name": "eq", "signature": "F eq G: FldFin, Rng -> BoolElt"}
  - {"name": "ne", "signature": "F ne G: FldFin, Rng -> BoolElt"}
  - {"name": "Roots", "signature": "Roots(f): RngUPolElt -> [ < FldFinElt, RngIntElt> ]"}
  - {"name": "RootsInSplittingField", "signature": "RootsInSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin"}
  - {"name": "FactorizationOverSplittingField", "signature": "FactorizationOverSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin"}
  - {"name": "FactorisationOverSplittingField", "signature": "FactorisationOverSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin"}
  - {"name": "RootOfUnity", "signature": "RootOfUnity(n, K): RngIntElt, FldFin -> FldFinElt"}
examples:
  - "ex-c6682e"
  - "ex-f06af7"
---

# Structure Operations

## Related Structures

<a id="function-category-fldfin"></a>
### `Category(F): FldFin -> Cat`

<a id="function-parent-fldfin"></a>
### `Parent(F): FldFin -> PowerStructure`

<a id="function-centre-fldfin"></a>
### `Centre(F): FldFin -> FldFin`

<a id="function-primering-fldfin"></a>
### `PrimeRing(F): FldFin -> FldFin`

<a id="function-primefield-fldfin-2"></a>
### `PrimeField(F): FldFin -> FldFin`

<a id="function-fieldoffractions-fldfin"></a>
### `FieldOfFractions(F): FldFin -> FldFin`

<a id="function-additivegroup-fldfin"></a>
### `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$.

<a id="function-multiplicativegroup-fldfin"></a>
### `MultiplicativeGroup(F): FldFin -> GrpAb, Map`

<a id="function-unitgroup-fldfin"></a>
### `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$.

<a id="function-set-fldfin"></a>
### `Set(F): FldFin -> SetEnum`

Create the enumerated set consisting of the elements of finite field $F$.

<a id="function-vectorspace-fldfin-fldfin"></a>
### `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.

<a id="function-vectorspace-fldfin-fldfin-fldfinelt"></a>
### `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.

<a id="function-matrixalgebra-fldfin-fldfin"></a>
### `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$.

<a id="function-matrixalgebra-algmat-fldfin"></a>
### `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.

<a id="example-ex-c6682e"></a>
### `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:

```magma
> 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)
```

<a id="function-galoisgroup-fldfin-fldfin"></a>
### `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.

<a id="function-automorphismgroup-fldfin-fldfin"></a>
### `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

<a id="function-characteristic-fldfin"></a>
### `Characteristic(F): FldFin -> RngIntElt`

<a id="operation-operation-fldfin-fldfinelt"></a>
### `# F: FldFin -> FldFinElt`

<a id="function-degree-fldfin"></a>
### `Degree(F): FldFin -> RngIntElt`

The absolute degree of $F$, that is, the degree over its prime subfield.

<a id="function-degree-fldfin-fldfin"></a>
### `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

<a id="function-definingpolynomial-fldfin"></a>
### `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`.

<a id="function-definingpolynomial-fldfin-2"></a>
### `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

<a id="function-isconway-fldfin"></a>
### `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.

<a id="function-isdefault-fldfin"></a>
### `IsDefault(F): FldFin -> BoolElt`

Given a finite field $F$, this function returns `true` iff $F$ is a default field.

<a id="function-iscommutative-fldfin"></a>
### `IsCommutative(F): FldFin -> BoolElt`

<a id="function-isunitary-fldfin"></a>
### `IsUnitary(F): FldFin -> BoolElt`

<a id="function-isfinite-fldfin"></a>
### `IsFinite(F): FldFin -> BoolElt`

<a id="function-isordered-fldfin"></a>
### `IsOrdered(F): FldFin -> BoolElt`

<a id="function-isfield-fldfin"></a>
### `IsField(F): FldFin -> BoolElt`

<a id="function-iseuclideandomain-fldfin"></a>
### `IsEuclideanDomain(F): FldFin -> BoolElt`

<a id="function-ispid-fldfin"></a>
### `IsPID(F): FldFin -> BoolElt`

<a id="function-isufd-fldfin"></a>
### `IsUFD(F): FldFin -> BoolElt`

<a id="function-isdivisionring-fldfin"></a>
### `IsDivisionRing(F): FldFin -> BoolElt`

<a id="function-iseuclideanring-fldfin"></a>
### `IsEuclideanRing(F): FldFin -> BoolElt`

<a id="function-isprincipalidealring-fldfin"></a>
### `IsPrincipalIdealRing(F): FldFin -> BoolElt`

<a id="function-isdomain-fldfin"></a>
### `IsDomain(F): FldFin -> BoolElt`

<a id="operation-op-eq-fldfin-rng"></a>
### `F eq G: FldFin, Rng -> BoolElt`

<a id="operation-op-ne-fldfin-rng"></a>
### `F ne G: FldFin, Rng -> BoolElt`

## Roots

<a id="function-roots-rngupolelt"></a>
### `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.

<a id="function-rootsinsplittingfield-rngupolelt-fldfin"></a>
### `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.

<a id="function-factorizationoversplittingfield-rngupolelt-fldfin"></a>
### `FactorizationOverSplittingField(f): RngUPolElt[FldFin] -> [<RngUPolElt, RngIntElt>], FldFin`

<a id="function-factorisationoversplittingfield-rngupolelt-fldfin"></a>
### `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.

<a id="function-rootofunity-rngintelt-fldfin"></a>
### `RootOfUnity(n, K): RngIntElt, FldFin -> FldFinElt`

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

<a id="example-ex-f06af7"></a>
### `Example: Roots in a Splitting Field (ex-f06af7)`

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

```magma
> 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.

```magma
> 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 ]
```
