# FiniteAlgebraicExtensionField F¶

- 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 Magma
- *: (%, 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 VectorSpace F
- =: (%, %) -> Boolean
- from BasicType
- ^: (%, Integer) -> %
- from DivisionRing
- ^: (%, NonNegativeInteger) -> %
- from MagmaWithUnit
- ^: (%, PositiveInteger) -> %
- from Magma
- ~=: (%, %) -> Boolean
- from BasicType
- algebraic?: % -> Boolean
- from ExtensionField F
- annihilate?: (%, %) -> Boolean
- from Rng
- antiCommutator: (%, %) -> %
- from NonAssociativeSemiRng
- associates?: (%, %) -> Boolean
- from EntireRing
- associator: (%, %, %) -> %
- from NonAssociativeRng

- basis: () -> Vector %
`basis()`

returns a fixed basis of % as`F`

-vector space.

- basis: PositiveInteger -> Vector %
`basis(n)`

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

-vector space.- characteristic: () -> NonNegativeInteger
- from NonAssociativeRing
- charthRoot: % -> % if F has Finite
- from FiniteFieldCategory
- charthRoot: % -> Union(%, failed) if F has Finite or F has CharacteristicNonZero
- from CharacteristicNonZero
- coerce: % -> %
- from Algebra %
- coerce: % -> OutputForm
- from CoercibleTo OutputForm
- coerce: F -> %
- from RetractableTo F
- coerce: Fraction Integer -> %
- from Algebra Fraction Integer
- coerce: Integer -> %
- from NonAssociativeRing
- commutator: (%, %) -> %
- from NonAssociativeRng
- conditionP: Matrix % -> Union(Vector %, failed) if F has Finite
- from PolynomialFactorizationExplicit
- convert: % -> InputForm if F has Finite
- from ConvertibleTo InputForm

- coordinates: % -> Vector F
`coordinates(a)`

returns the coordinates of`a`

with respect to the fixed`F`

-vector space basis.

- coordinates: Vector % -> Matrix F
`coordinates([v1, ..., vm])`

returns the coordinates of the`vi`

`'s`

with to the fixed basis. The coordinates of`vi`

are contained in the`i`

th row of the matrix returned by this function.

- 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
- dimension: () -> CardinalNumber
- from VectorSpace F
- discreteLog: % -> NonNegativeInteger if F has Finite
- from FiniteFieldCategory
- discreteLog: (%, %) -> Union(NonNegativeInteger, failed) if F has Finite or F has CharacteristicNonZero
- from FieldOfPrimeCharacteristic
- divide: (%, %) -> Record(quotient: %, remainder: %)
- from EuclideanDomain
- enumerate: () -> List % if F has Finite
- from Finite
- 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.- factor: % -> Factored %
- from UniqueFactorizationDomain
- factorPolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite
- from PolynomialFactorizationExplicit
- factorsOfCyclicGroupSize: () -> List Record(factor: Integer, exponent: Integer) if F has Finite
- from FiniteFieldCategory
- factorSquareFreePolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite
- from PolynomialFactorizationExplicit
- Frobenius: % -> % if F has Finite
- from ExtensionField F
- Frobenius: (%, NonNegativeInteger) -> % if F has Finite
- from ExtensionField F
- gcd: (%, %) -> %
- from GcdDomain
- gcd: List % -> %
- from GcdDomain
- gcdPolynomial: (SparseUnivariatePolynomial %, SparseUnivariatePolynomial %) -> SparseUnivariatePolynomial %
- from GcdDomain

- 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
- lcm: (%, %) -> %
- from GcdDomain
- lcm: List % -> %
- from GcdDomain
- 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
`minimalPolynomial(a)`

returns the minimal polynomial of an element`a`

over the ground field`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
`norm(a)`

computes the norm of`a`

with respect to the field considered as an algebra with 1 over the ground field`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 Finite or F has CharacteristicNonZero
- from FieldOfPrimeCharacteristic
- order: % -> PositiveInteger if F has Finite
- from FiniteFieldCategory
- prime?: % -> Boolean
- from UniqueFactorizationDomain
- primeFrobenius: % -> % if F has Finite or F has CharacteristicNonZero
- from FieldOfPrimeCharacteristic
- primeFrobenius: (%, NonNegativeInteger) -> % if F has Finite or F has CharacteristicNonZero
- from FieldOfPrimeCharacteristic
- 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
- random: () -> % if F has Finite
- from Finite
- recip: % -> Union(%, failed)
- from MagmaWithUnit
- rem: (%, %) -> %
- from EuclideanDomain
- representationType: () -> Union(prime, polynomial, normal, cyclic) if F has Finite
- from FiniteFieldCategory

- represents: Vector F -> %
`represents([a1, .., an])`

returns`a1*v1 + ... + an*vn`

, where`v1`

, …,`vn`

are the elements of the fixed basis.- 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
- from PolynomialFactorizationExplicit
- squareFree: % -> Factored %
- from UniqueFactorizationDomain
- squareFreePart: % -> %
- from UniqueFactorizationDomain
- squareFreePolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite
- from PolynomialFactorizationExplicit
- subtractIfCan: (%, %) -> Union(%, failed)
- from CancellationAbelianMonoid
- tableForDiscreteLogarithm: Integer -> Table(PositiveInteger, NonNegativeInteger) if F has Finite
- from FiniteFieldCategory

- trace: % -> F
`trace(a)`

computes the trace of`a`

with respect to the field considered as an algebra with 1 over the ground field`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])`

.- 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 %

BiModule(%, %)

BiModule(F, F)

BiModule(Fraction Integer, Fraction Integer)

CharacteristicNonZero if F has Finite or F has CharacteristicNonZero

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 Finite or F has CharacteristicNonZero

FiniteFieldCategory if F has Finite

Module %

Module F

PolynomialFactorizationExplicit if F has Finite

StepThrough if F has Finite