FiniteAlgebraicExtensionField FΒΆ

ffcat.spad line 92 [edit on github]

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

=: (%, %) -> 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 CharacteristicNonZero or F has Finite

from PolynomialFactorizationExplicit

coerce: % -> %

from Algebra %

coerce: % -> OutputForm

from CoercibleTo OutputForm

coerce: F -> %

from Algebra 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

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

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

from FieldOfPrimeCharacteristic

order: % -> PositiveInteger if F has Finite

from FiniteFieldCategory

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

AbelianGroup

AbelianMonoid

AbelianSemiGroup

Algebra %

Algebra F

Algebra Fraction Integer

BasicType

BiModule(%, %)

BiModule(F, F)

BiModule(Fraction Integer, Fraction Integer)

CancellationAbelianMonoid

canonicalsClosed

canonicalUnitNormal

CharacteristicNonZero if F has CharacteristicNonZero or F has Finite

CharacteristicZero if F has CharacteristicZero

CoercibleFrom F

CoercibleTo OutputForm

CommutativeRing

CommutativeStar

Comparable if F has Finite

ConvertibleTo InputForm if F has Finite

DifferentialRing if F has Finite

DivisionRing

EntireRing

EuclideanDomain

ExtensionField F

Field

FieldOfPrimeCharacteristic if F has CharacteristicNonZero or F has Finite

Finite if F has Finite

FiniteFieldCategory if F has Finite

FiniteRankAlgebra(F, SparseUnivariatePolynomial F)

FramedAlgebra(F, SparseUnivariatePolynomial F)

FramedModule F

GcdDomain

IntegralDomain

LeftModule %

LeftModule F

LeftModule Fraction Integer

LeftOreRing

Magma

MagmaWithUnit

Module %

Module F

Module Fraction Integer

Monoid

NonAssociativeRing

NonAssociativeRng

NonAssociativeSemiRing

NonAssociativeSemiRng

noZeroDivisors

PolynomialFactorizationExplicit if F has Finite

PrincipalIdealDomain

RetractableTo F

RightModule %

RightModule F

RightModule Fraction Integer

Ring

Rng

SemiGroup

SemiRing

SemiRng

SetCategory

StepThrough if F has Finite

TwoSidedRecip

UniqueFactorizationDomain

unitsKnown