FiniteAlgebraicExtensionField F¶

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) -> %
*: (F, %) -> %

from LeftModule F

*: (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: (%, %) -> %
associates?: (%, %) -> Boolean

from EntireRing

associator: (%, %, %) -> %
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
characteristicPolynomial: % -> SparseUnivariatePolynomial F
charthRoot: % -> % if F has Finite
charthRoot: % -> Union(%, failed) if F has CharacteristicNonZero or F has Finite
coerce: % -> %

from Algebra %

coerce: % -> OutputForm
coerce: F -> %

from Algebra F

coerce: Fraction Integer -> %
coerce: Integer -> %
commutator: (%, %) -> %
conditionP: Matrix % -> Union(Vector %, failed) if F has Finite
convert: % -> InputForm if F has Finite
convert: % -> Vector F

from FramedModule F

convert: Vector F -> %

from FramedModule F

coordinates: % -> Vector F

from FramedModule F

coordinates: (%, Vector %) -> Vector F
coordinates: (Vector %, Vector %) -> Matrix 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 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 discreteLog: (%, %) -> Union(NonNegativeInteger, failed) if F has CharacteristicNonZero or F has Finite discriminant: () -> F discriminant: Vector % -> F divide: (%, %) -> Record(quotient: %, remainder: %) from EuclideanDomain enumerate: () -> List % if F has Finite from Finite euclideanSize: % -> NonNegativeInteger from EuclideanDomain expressIdealMember: (List %, %) -> Union(List %, failed) 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 % factorPolynomial: SparseUnivariatePolynomial % -> Factored SparseUnivariatePolynomial % if F has Finite factorsOfCyclicGroupSize: () -> List Record(factor: Integer, exponent: NonNegativeInteger) if F has Finite 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 gcd: (%, %) -> % from GcdDomain gcd: List % -> % from GcdDomain 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 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: (%, 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: (%, 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
prime?: % -> Boolean
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
primitiveElement: () -> % if F has Finite
principalIdeal: List % -> Record(coef: List %, generator: %)
quo: (%, %) -> %

from EuclideanDomain

random: () -> % if F has Finite

from Finite

rank: () -> PositiveInteger
recip: % -> Union(%, failed)

from MagmaWithUnit

regularRepresentation: % -> Matrix F
regularRepresentation: (%, Vector %) -> Matrix F
rem: (%, %) -> %

from EuclideanDomain

representationType: () -> Union(prime, polynomial, normal, cyclic) if F has Finite
represents: (Vector F, Vector %) -> %
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
trace: % -> 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
traceMatrix: Vector % -> Matrix 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

AbelianGroup

AbelianMonoid

AbelianSemiGroup

BasicType

BiModule(%, %)

BiModule(F, F)

CancellationAbelianMonoid

canonicalsClosed

canonicalUnitNormal

CharacteristicNonZero if F has CharacteristicNonZero or F has Finite

CommutativeRing

CommutativeStar

Comparable if F has Finite

ConvertibleTo InputForm if F has Finite

DifferentialRing if F has Finite

DivisionRing

EntireRing

EuclideanDomain

Field

FieldOfPrimeCharacteristic if F has CharacteristicNonZero or F has Finite

Finite if F has Finite

FiniteFieldCategory if F has Finite

GcdDomain

IntegralDomain

LeftOreRing

Magma

MagmaWithUnit

Monoid

NonAssociativeRing

NonAssociativeRng

NonAssociativeSemiRing

NonAssociativeSemiRng

noZeroDivisors

PrincipalIdealDomain

Ring

Rng

SemiGroup

SemiRing

SemiRng

SetCategory

StepThrough if F has Finite

TwoSidedRecip

UniqueFactorizationDomain

unitsKnown