# FiniteAlgebraicExtensionField FΒΆ

ffcat.spad line 92 [edit on github]

F: Field

FiniteAlgebraicExtensionField *F* is the category of fields which are finite algebraic extensions of the field *F*. If *F* is finite then any finite algebraic extension of *F* is finite, too. Let *K* be a finite algebraic extension of the finite field *F*. The exponentiation of elements of *K* defines a `Z`

-module structure on the multiplicative group of *K*. The additive group of *K* becomes a module over the ring of polynomials over *F* via the operation linearAssociatedExp(a: `K`

, `f:`

SparseUnivariatePolynomial `F`

) which is linear over *F*, i.e. for elements *a* from *K*, *c, d* from *F* and *f, g* univariate polynomials over *F* we have linearAssociatedExp(a, cf+dg) equals *c* times linearAssociatedExp(a, `f`

) plus *d* times linearAssociatedExp(a, `g`

). Therefore linearAssociatedExp is defined completely by its action on monomials from *F[X]*: linearAssociatedExp(a, monomial(1, `k`

)`\$`

SUP(`F`

)) is defined to be Frobenius(a, `k`

) which is *a^(q^k)* where *q=size()$F*. The operations order and discreteLog associated with the multiplicative exponentiation have additive analogues associated to the operation linearAssociatedExp. These are the functions linearAssociatedOrder and linearAssociatedLog, respectively.

- 0: %
from AbelianMonoid

- 1: %
from MagmaWithUnit

- *: (%, %) -> %
from LeftModule %

- *: (%, F) -> %
from RightModule F

- *: (%, Fraction Integer) -> %
from RightModule Fraction Integer

- *: (F, %) -> %
from LeftModule F

- *: (Fraction Integer, %) -> %
from LeftModule Fraction Integer

- *: (Integer, %) -> %
from AbelianGroup

- *: (NonNegativeInteger, %) -> %
from AbelianMonoid

- *: (PositiveInteger, %) -> %
from AbelianSemiGroup

- +: (%, %) -> %
from AbelianSemiGroup

- -: % -> %
from AbelianGroup

- -: (%, %) -> %
from AbelianGroup

- /: (%, %) -> %
from Field

- /: (%, F) -> %
from ExtensionField F

- ^: (%, Integer) -> %
from DivisionRing

- ^: (%, NonNegativeInteger) -> %
from MagmaWithUnit

- ^: (%, PositiveInteger) -> %
from Magma

- algebraic?: % -> Boolean
from ExtensionField F

- annihilate?: (%, %) -> Boolean
from Rng

- antiCommutator: (%, %) -> %

- associates?: (%, %) -> Boolean
from EntireRing

- associator: (%, %, %) -> %
from NonAssociativeRng

- basis: () -> Vector %
from FramedModule F

- basis: PositiveInteger -> Vector % if F has Finite
`basis(n)`

returns a fixed basis of a subfield of % as`F`

-vector space.

- characteristic: () -> NonNegativeInteger
from NonAssociativeRing

- characteristicPolynomial: % -> SparseUnivariatePolynomial F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- charthRoot: % -> % if F has Finite
from FiniteFieldCategory

- charthRoot: % -> Union(%, failed) if F has CharacteristicNonZero or F has Finite

- coerce: % -> %
from Algebra %

- coerce: % -> OutputForm
from CoercibleTo OutputForm

- coerce: F -> %
from Algebra F

- coerce: Fraction Integer -> %
- coerce: Integer -> %
from NonAssociativeRing

- commutator: (%, %) -> %
from NonAssociativeRng

- conditionP: Matrix % -> Union(Vector %, failed) if F has Finite

- convert: % -> InputForm if F has Finite
from ConvertibleTo InputForm

- convert: % -> Vector F
from FramedModule F

- convert: Vector F -> %
from FramedModule F

- coordinates: % -> Vector F
from FramedModule F

- coordinates: (%, Vector %) -> Vector F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- coordinates: (Vector %, Vector %) -> Matrix F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- coordinates: Vector % -> Matrix F
from FramedModule F

- createNormalElement: () -> % if F has Finite
`createNormalElement()`

computes a normal element over the ground field`F`

, that is,`a^(q^i), 0 <= i < extensionDegree()`

is an`F`

-basis, where`q = size()\$F`

. Reference: Such an element exists Lidl/Niederreiter: Theorem 2.35.

- createPrimitiveElement: () -> % if F has Finite
from FiniteFieldCategory

- D: % -> % if F has Finite
from DifferentialRing

- D: (%, NonNegativeInteger) -> % if F has Finite
from DifferentialRing

- definingPolynomial: () -> SparseUnivariatePolynomial F
`definingPolynomial()`

returns the polynomial used to define the field extension.

- degree: % -> OnePointCompletion PositiveInteger
from ExtensionField F

- degree: % -> PositiveInteger
`degree(a)`

returns the degree of the minimal polynomial of an element`a`

over the ground field`F`

.

- differentiate: % -> % if F has Finite
from DifferentialRing

- differentiate: (%, NonNegativeInteger) -> % if F has Finite
from DifferentialRing

- discreteLog: % -> NonNegativeInteger if F has Finite
from FiniteFieldCategory

- discreteLog: (%, %) -> Union(NonNegativeInteger, failed) if F has CharacteristicNonZero or F has Finite

- discriminant: () -> F
from FramedAlgebra(F, SparseUnivariatePolynomial F)

- discriminant: Vector % -> F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- divide: (%, %) -> Record(quotient: %, remainder: %)
from EuclideanDomain

- euclideanSize: % -> NonNegativeInteger
from EuclideanDomain

- expressIdealMember: (List %, %) -> Union(List %, failed)
from PrincipalIdealDomain

- exquo: (%, %) -> Union(%, failed)
from EntireRing

- extendedEuclidean: (%, %) -> Record(coef1: %, coef2: %, generator: %)
from EuclideanDomain

- extendedEuclidean: (%, %, %) -> Union(Record(coef1: %, coef2: %), failed)
from EuclideanDomain

- extensionDegree: () -> OnePointCompletion PositiveInteger
from ExtensionField F

- extensionDegree: () -> PositiveInteger
`extensionDegree()`

returns the degree of field extension.

- factorPolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite

- factorsOfCyclicGroupSize: () -> List Record(factor: Integer, exponent: NonNegativeInteger) if F has Finite
from FiniteFieldCategory

- factorSquareFreePolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite

- Frobenius: % -> % if F has Finite
from ExtensionField F

- Frobenius: (%, NonNegativeInteger) -> % if F has Finite
from ExtensionField F

- gcdPolynomial: (SparseUnivariatePolynomial %, SparseUnivariatePolynomial %) -> SparseUnivariatePolynomial %

- generator: () -> % if F has Finite
`generator()`

returns a root of the defining polynomial. This element generates the field as an algebra over the ground field.

- hash: % -> SingleInteger
from SetCategory

- hashUpdate!: (HashState, %) -> HashState
from SetCategory

- index: PositiveInteger -> % if F has Finite
from Finite

- inGroundField?: % -> Boolean
from ExtensionField F

- init: % if F has Finite
from StepThrough

- inv: % -> %
from DivisionRing

- latex: % -> String
from SetCategory

- lcmCoef: (%, %) -> Record(llcm_res: %, coeff1: %, coeff2: %)
from LeftOreRing

- leftPower: (%, NonNegativeInteger) -> %
from MagmaWithUnit

- leftPower: (%, PositiveInteger) -> %
from Magma

- leftRecip: % -> Union(%, failed)
from MagmaWithUnit

- linearAssociatedExp: (%, SparseUnivariatePolynomial F) -> % if F has Finite
`linearAssociatedExp(a, f)`

is linear over*F*, i.e. for elements*a*from*$*,*c, d*form*F*and*f, g*univariate polynomials over*F*we have linearAssociatedExp(a, cf+dg) equals*c*times linearAssociatedExp(a,`f`

) plus*d*times linearAssociatedExp(a,`g`

). Therefore linearAssociatedExp is defined completely by its action on monomials from*F[X]*: linearAssociatedExp(a, monomial(1,`k`

)`\$`

SUP(`F`

)) is defined to be Frobenius(a,`k`

) which is*a^(q^k)*, where*q=size()$F*.

- linearAssociatedLog: % -> SparseUnivariatePolynomial F if F has Finite
`linearAssociatedLog(a)`

returns a polynomial*g*, such that linearAssociatedExp(normalElement(),`g`

) equals*a*.

- linearAssociatedLog: (%, %) -> Union(SparseUnivariatePolynomial F, failed) if F has Finite
`linearAssociatedLog(b, a)`

returns a polynomial*g*, such that the linearAssociatedExp(`b`

,`g`

) equals*a*. If there is no such polynomial*g*, then linearAssociatedLog fails.

- linearAssociatedOrder: % -> SparseUnivariatePolynomial F if F has Finite
`linearAssociatedOrder(a)`

retruns the monic polynomial*g*of least degree, such that linearAssociatedExp(a,`g`

) is 0.

- lookup: % -> PositiveInteger if F has Finite
from Finite

- minimalPolynomial: % -> SparseUnivariatePolynomial F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- minimalPolynomial: (%, PositiveInteger) -> SparseUnivariatePolynomial % if F has Finite
`minimalPolynomial(x, n)`

computes the minimal polynomial of`x`

over the field of extension degree`n`

over the ground field`F`

.

- multiEuclidean: (List %, %) -> Union(List %, failed)
from EuclideanDomain

- nextItem: % -> Union(%, failed) if F has Finite
from StepThrough

- norm: % -> F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- norm: (%, PositiveInteger) -> % if F has Finite
`norm(a, d)`

computes the norm of`a`

with respect to the field of extension degree`d`

over the ground field of size. Error: if`d`

does not divide the extension degree of`a`

. Note: norm(a,`d`

) = reduce(*, [a^(`q^`

(d*i)) for`i`

in 0..`n/d`

])

- normal?: % -> Boolean if F has Finite
`normal?(a)`

tests whether the element`a`

is normal over the ground field`F`

, i.e.`a^(q^i), 0 <= i <= extensionDegree()-1`

is an`F`

-basis, where`q = size()\$F`

. Implementation according to Lidl/Niederreiter: Theorem 2.39.

- normalElement: () -> % if F has Finite
`normalElement()`

returns a element, normal over the ground field`F`

, i.e.`a^(q^i), 0 <= i < extensionDegree()`

is an`F`

-basis, where`q = size()\$F`

. At the first call, the element is computed by createNormalElement then cached in a global variable. On subsequent calls, the element is retrieved by referencing the global variable.

- one?: % -> Boolean
from MagmaWithUnit

- opposite?: (%, %) -> Boolean
from AbelianMonoid

- order: % -> OnePointCompletion PositiveInteger if F has CharacteristicNonZero or F has Finite
- order: % -> PositiveInteger if F has Finite
from FiniteFieldCategory

- primeFrobenius: % -> % if F has CharacteristicNonZero or F has Finite
- primeFrobenius: (%, NonNegativeInteger) -> % if F has CharacteristicNonZero or F has Finite

- primitive?: % -> Boolean if F has Finite
from FiniteFieldCategory

- primitiveElement: () -> % if F has Finite
from FiniteFieldCategory

- principalIdeal: List % -> Record(coef: List %, generator: %)
from PrincipalIdealDomain

- quo: (%, %) -> %
from EuclideanDomain

- rank: () -> PositiveInteger
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- recip: % -> Union(%, failed)
from MagmaWithUnit

- regularRepresentation: % -> Matrix F
from FramedAlgebra(F, SparseUnivariatePolynomial F)

- regularRepresentation: (%, Vector %) -> Matrix F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- rem: (%, %) -> %
from EuclideanDomain

- representationType: () -> Union(prime, polynomial, normal, cyclic) if F has Finite
from FiniteFieldCategory

- represents: (Vector F, Vector %) -> %
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- represents: Vector F -> %
from FramedModule F

- retract: % -> F
from RetractableTo F

- retractIfCan: % -> Union(F, failed)
from RetractableTo F

- rightPower: (%, NonNegativeInteger) -> %
from MagmaWithUnit

- rightPower: (%, PositiveInteger) -> %
from Magma

- rightRecip: % -> Union(%, failed)
from MagmaWithUnit

- sample: %
from AbelianMonoid

- size: () -> NonNegativeInteger if F has Finite
from Finite

- sizeLess?: (%, %) -> Boolean
from EuclideanDomain

- smaller?: (%, %) -> Boolean if F has Finite
from Comparable

- solveLinearPolynomialEquation: (List SparseUnivariatePolynomial %, SparseUnivariatePolynomial %) -> Union(List SparseUnivariatePolynomial %, failed) if F has Finite

- squareFree: % -> Factored %

- squareFreePart: % -> %

- squareFreePolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite

- subtractIfCan: (%, %) -> Union(%, failed)

- tableForDiscreteLogarithm: Integer -> Table(PositiveInteger, NonNegativeInteger) if F has Finite
from FiniteFieldCategory

- trace: % -> F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- trace: (%, PositiveInteger) -> % if F has Finite
`trace(a, d)`

computes the trace of`a`

with respect to the field of extension degree`d`

over the ground field of size`q`

. Error: if`d`

does not divide the extension degree of`a`

. Note:`trace(a, d) = reduce(+, [a^(q^(d*i)) for i in 0..n/d])`

.

- traceMatrix: () -> Matrix F
from FramedAlgebra(F, SparseUnivariatePolynomial F)

- traceMatrix: Vector % -> Matrix F
from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

- transcendenceDegree: () -> NonNegativeInteger
from ExtensionField F

- transcendent?: % -> Boolean
from ExtensionField F

- unit?: % -> Boolean
from EntireRing

- unitCanonical: % -> %
from EntireRing

- unitNormal: % -> Record(unit: %, canonical: %, associate: %)
from EntireRing

- zero?: % -> Boolean
from AbelianMonoid

Algebra %

Algebra F

BiModule(%, %)

BiModule(F, F)

BiModule(Fraction Integer, Fraction Integer)

CharacteristicNonZero if F has CharacteristicNonZero or F has Finite

CharacteristicZero if F has CharacteristicZero

Comparable if F has Finite

ConvertibleTo InputForm if F has Finite

DifferentialRing if F has Finite

FieldOfPrimeCharacteristic if F has CharacteristicNonZero or F has Finite

FiniteFieldCategory if F has Finite

FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

FramedAlgebra(F, SparseUnivariatePolynomial F)

Module %

Module F

PolynomialFactorizationExplicit if F has Finite

StepThrough if F has Finite