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 ExtensionField 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 %: 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 Finite or F has CharacteristicNonZero: from PolynomialFactorizationExplicit

coerce: % -> %: from Algebra %
coerce: % -> OutputForm: from CoercibleTo OutputForm
coerce: F -> %: from CoercibleFrom 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
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: from FieldOfPrimeCharacteristic

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

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: NonNegativeInteger) 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 PolynomialFactorizationExplicit

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 if F has Hashable: from Hashable

hashUpdate!: (HashState, %) -> HashState if F has Hashable: from Hashable

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) returns 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 intermediate field of extension degree d over the ground field F. Error: if d does not divide the extension degree n of \%. Note: norm(a, d) = reduce(*, [a^(q^(d*i)) for i in 0..n/d]) where q is size of F.

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: from FieldOfPrimeCharacteristic
order: % -> PositiveInteger if F has Finite: from FiniteFieldCategory

plenaryPower: (%, PositiveInteger) -> %: from NonAssociativeAlgebra %

prime?: % -> Boolean: from UniqueFactorizationDomain

primeFrobenius: % -> % if F has CharacteristicNonZero or F has Finite: from FieldOfPrimeCharacteristic
primeFrobenius: (%, NonNegativeInteger) -> % if F has CharacteristicNonZero or F has Finite: 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

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: 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: from FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

trace: (%, PositiveInteger) -> % if F has Finite: trace(a, d) computes the trace of a with respect to the intermediate field of extension degree d over the ground field F. Error: if d does not divide the extension degree n of \%. Note: trace(a, d) = reduce(+, [a^(q^(d*i)) for i in 0..n/d]) where q is size of F.