# 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: 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 := ext< F7 | 2 >; > F := 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) ``` ### `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] -> [], 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] -> [], FldFin` ### `FactorisationOverSplittingField(f): RngUPolElt[FldFin] -> [], 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: Functions (ex-f06af7)` We compute the roots of a certain degree-20 polynomial $f$ in its minimal splitting field. ```magma > K := GF(2); > P := PolynomialRing(GF(2)); > f := x^20 + x^11 + 1; > Factorization(f); [ , , ] > time r, S := 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]; > [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 ] ```