ExtensionFieldsImpl.mesa
Last Edited by: Arnon, June 10, 1985 4:19:22 pm PDT
DIRECTORY
Rope,
Basics,
Ascii,
IO,
AlgebraClasses,
RatIntervals,
Variables,
DistribPolys,
Polynomials,
AlgebraicNumbers,
ExtensionFields;
ExtensionFieldsImpl: CEDAR PROGRAM
IMPORTS Rope, IO, RatIntervals, DistribPolys, Polynomials
EXPORTS ExtensionFields =
BEGIN OPEN AC: AlgebraClasses, RI: RatIntervals, VARS: Variables, DP: DistribPolys, POL: Polynomials, AN: AlgebraicNumbers, ExtensionFields;
Errors
SyntaxError: PUBLIC ERROR [reason: ATOM] = CODE;
BadGroundField: PUBLIC ERROR [elementStructure: AC.Structure] = CODE;
Classes for ExtensionFields
ClassPrintName: AC.PrintNameProc = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
minPolyRing: AC.Structure ← data.primitiveElement.minPolyRing;
IF NOT data.primitiveElement.real THEN
RETURN[Rope.Cat[
"Extension of ",
data.groundField.class.printName[data.groundField],
" by root of ",
minPolyRing.class.toRope[data.primitiveElement.minimalPolynomial, minPolyRing]
] ]
ELSE {
out: Rope.ROPE ← Rope.Cat[
"Extension of ",
data.groundField.class.printName[data.groundField],
" by the unique root of ",
minPolyRing.class.toRope[data.primitiveElement.minimalPolynomial, minPolyRing]
];
out ← Rope.Cat[out, " in ", RI.RatIntervalToRope[data.primitiveElement.isolatingInterval] ];
RETURN[out];
};
};
ClassLegalFirstChar: AC.LegalFirstCharOp = {
SELECT char FROM
'[, '( => RETURN[TRUE];
ENDCASE;
RETURN[FALSE];
};
ClassRead: AC.ReadOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ReadExtensionFieldElement[in, data.primitiveElement, FALSE] ];
};
ClassFromRope: AC.FromRopeOp = {
stream: IO.STREAM ← IO.RIS[in];
RETURN[ ClassRead[stream, structure] ];
};
ClassToRope: AC.ToRopeOp = {
fieldElement: ExtensionFieldElement ← NARROW[in];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ ExtensionFieldElementToRope[fieldElement, data.primitiveElement] ]
};
ClassWrite: AC.WriteOp = {
IO.PutRope[stream, ClassToRope[in, structure] ]
};
ClassZero: AC.NullaryOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ data.primitiveElement.minPolyRing.class.zero[data.primitiveElement.minPolyRing] ]
};
ClassOne: AC.NullaryOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ data.primitiveElement.minPolyRing.class.one[data.primitiveElement.minPolyRing] ]
};
ClassCharacteristic: AC.StructureRankOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ data.primitiveElement.minPolyRing.class.characteristic[data.primitiveElement.minPolyRing] ]
};
ClassAdd: AC.BinaryOp = {
firstFieldElement: ExtensionFieldElement ← NARROW[firstArg];
secondFieldElement: ExtensionFieldElement ← NARROW[secondArg];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ Add[firstFieldElement, secondFieldElement, data.groundField] ]
};
ClassNegate: AC.UnaryOp = {
fieldElement: ExtensionFieldElement ← NARROW[arg];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ Negate[fieldElement, data.groundField] ]
};
ClassSubtract: AC.BinaryOp = {
firstFieldElement: ExtensionFieldElement ← NARROW[firstArg];
secondFieldElement: ExtensionFieldElement ← NARROW[secondArg];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ Subtract[firstFieldElement, secondFieldElement, data.groundField] ]
};
ClassMultiply: AC.BinaryOp = {
firstFieldElement: ExtensionFieldElement ← NARROW[firstArg];
secondFieldElement: ExtensionFieldElement ← NARROW[secondArg];
RETURN[ Multiply[firstFieldElement, secondFieldElement, structure] ]
};
ClassInvert: AC.UnaryOp = {
fieldElement: ExtensionFieldElement ← NARROW[arg];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ Invert[fieldElement, data.groundField] ]
};
ClassDivide: AC.BinaryOp = {
firstFieldElement: ExtensionFieldElement ← NARROW[firstArg];
secondFieldElement: ExtensionFieldElement ← NARROW[secondArg];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ Divide[firstFieldElement, secondFieldElement, data.groundField] ]
};
ClassScalarMultiply: AC.BinaryOp = {
scalar: REF ← firstArg;
inExtensionField: ExtensionFieldElement ← NARROW[secondArg];
RETURN[ ScalarMultiply[scalar, inExtensionField, structure] ]
};
ClassEqual: AC.EqualityOp = {
firstFieldElement: ExtensionFieldElement ← NARROW[firstArg];
secondFieldElement: ExtensionFieldElement ← NARROW[secondArg];
data: ExtensionFieldData ← NARROW[structure.instanceData];
RETURN[ Equal[firstFieldElement, secondFieldElement, data.groundField] ]
};
generalExtensionFieldClass: PUBLIC AC.StructureClass ← NEW[AC.StructureClassRec ← [
flavor: divisionAlgebra,
printName: ClassPrintName,
legalFirstChar: ClassLegalFirstChar,
read: ClassRead,
fromRope: ClassFromRope,
toRope: ClassToRope,
write: ClassWrite,
add: ClassAdd,
negate: ClassNegate,
subtract: ClassSubtract,
zero: ClassZero,
multiply: ClassMultiply,
invert: ClassInvert,
divide: ClassDivide,
one: ClassOne,
scalarMultiply: ClassScalarMultiply,
equal: ClassEqual,
characteristic: ClassCharacteristic,
propList: NIL
] ];
realExtensionFieldClass: PUBLIC AC.StructureClass ← NEW[AC.StructureClassRec ← [
flavor: divisionAlgebra,
printName: ClassPrintName,
legalFirstChar: ClassLegalFirstChar,
read: ClassRead,
fromRope: ClassFromRope,
toRope: ClassToRope,
write: ClassWrite,
add: ClassAdd,
negate: ClassNegate,
subtract: ClassSubtract,
zero: ClassZero,
multiply: ClassMultiply,
invert: ClassInvert,
divide: ClassDivide,
one: ClassOne,
scalarMultiply: ClassScalarMultiply,
equal: ClassEqual,
characteristic: ClassCharacteristic,
propList: NIL
] ];
ExtensionField Constructors
MakeExtensionField: PUBLIC PROC [primitiveElement: AN.AlgebraicNumber] RETURNS [extensionField: AC.Structure] ~ {
data: POL.PolynomialRingData ← NARROW[primitiveElement.minPolyRing.instanceData];
groundField: AC.Structure ← data.coeffRing;
extensionFieldData: ExtensionFieldData ← NEW[ExtensionFieldDataRec ← [
groundField: groundField,
primitiveElement: primitiveElement
] ];
IF groundField.class.flavor#field AND groundField.class.flavor#divisionAlgebra THEN ERROR BadGroundField[groundField];
IF NOT groundField.class.realField THEN
RETURN[ NEW[AC.StructureRec ← [
class: generalExtensionFieldClass,
instanceData: extensionFieldData
] ] ]
ELSE
RETURN[ NEW[AC.StructureRec ← [
class: realExtensionFieldClass,
instanceData: extensionFieldData
] ] ]
};
Check Properties
IsGeneralExtensionField: PUBLIC PROC [structure: AC.Structure] RETURNS [BOOL] ~ {
IF structure.class.flavor#field AND structure.class.flavor#divisionAlgebra THEN RETURN[FALSE];
IF ISTYPE[structure.instanceData, ExtensionFieldData] AND NOT structure.class.realField THEN RETURN[TRUE] ELSE RETURN[FALSE];
};
IsRealField: PUBLIC PROC [structure: AC.Structure] RETURNS [BOOL] ~ {
IF structure.class.flavor#field AND structure.class.flavor#divisionAlgebra THEN RETURN[FALSE];
IF structure.class.realField THEN RETURN[TRUE] ELSE RETURN[FALSE];
};
IsRealExtensionField: PUBLIC PROC [structure: AC.Structure] RETURNS [BOOL] ~ {
IF structure.class.flavor#field AND structure.class.flavor#divisionAlgebra THEN RETURN[FALSE];
IF ISTYPE[structure.instanceData, ExtensionFieldData] AND structure.class.realField THEN RETURN[TRUE] ELSE RETURN[FALSE];
};
Conversion and IO
ReadExtensionFieldElement: PUBLIC PROC [in: IO.STREAM, algebraicNumber: AN.AlgebraicNumber, reduced: BOOL ← FALSE] RETURNS [out: ExtensionFieldElement] ~ {
char: CHAR;
dElt: DP.DPolynomial;
data: POL.PolynomialRingData ← NARROW[algebraicNumber.minPolyRing.instanceData];
fieldElementVariable: VARS.VariableSeq ← data.variables;
[]← in.SkipWhitespace[];
char ← in.GetChar[];
IF char # '( AND char#'[ THEN ERROR; -- accept either curved (SAC-2) or square brackets
[dElt, char] ← DP.ReadDPoly[in, fieldElementVariable, data.coeffRing, DP.RightBracketProc]; -- terminated by a right bracket, not a dollar sign
out ← POL.PolyFromDPoly[ dElt, fieldElementVariable];
IF NOT reduced THEN out ← POL.Remainder[out, algebraicNumber.minimalPolynomial, algebraicNumber.minPolyRing];
};
ExtensionFieldElementFromRope: PUBLIC PROC [in: Rope.ROPE, algebraicNumber: AN.AlgebraicNumber, reduced: BOOL ← FALSE] RETURNS [out: ExtensionFieldElement] ~ {
out ← ReadExtensionFieldElement[IO.RIS[in], algebraicNumber, reduced];
};
ExtensionFieldElementToRope: PUBLIC PROC [in: ExtensionFieldElement, algebraicNumber: AN.AlgebraicNumber] RETURNS [out: Rope.ROPE] ~ {
out ← Rope.Concat["[ ", algebraicNumber.minPolyRing.class.toRope[in, algebraicNumber.minPolyRing ] ];
out ← Rope.Replace[out, Rope.Length[out]-2, 2, "]" ];
};
WriteExtensionFieldElement: PUBLIC PROC [in: ExtensionFieldElement, algebraicNumber: AN.AlgebraicNumber, out: IO.STREAM] ~ {
out.PutRope[ ExtensionFieldElementToRope[in, algebraicNumber] ]
};
Arithmetic
Add: PUBLIC PROC [in1, in2: ExtensionFieldElement, groundField: AC.Structure] RETURNS [out: ExtensionFieldElement] ~ {
RETURN[POL.Add[in1, in2, groundField] ];
};
Negate: PUBLIC PROC [in: ExtensionFieldElement, groundField: AC.Structure] RETURNS [out: ExtensionFieldElement] ~ {
RETURN[POL.Negate[in, groundField] ];
};
Subtract: PUBLIC PROC [in1, in2: ExtensionFieldElement, groundField: AC.Structure] RETURNS [ExtensionFieldElement] ~ {
RETURN[POL.Subtract[in1, in2, groundField] ];
};
Multiply: PUBLIC PROC [in1, in2: ExtensionFieldElement, extensionField: AC.Structure] RETURNS [out: ExtensionFieldElement] ~ {
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
temp: POL.Polynomial ← POL.Multiply[in1, in2, data.groundField];
RETURN[POL.Remainder[temp, data.primitiveElement.minimalPolynomial, data.primitiveElement.minPolyRing ] ];
};
Invert: PUBLIC PROC [in: ExtensionFieldElement, algebraicNumber: AN.AlgebraicNumber] RETURNS [out: ExtensionFieldElement] ~ {
Divide: PUBLIC PROC [in1, in2: ExtensionFieldElement, algebraicNumber: AN.AlgebraicNumber] RETURNS [out: ExtensionFieldElement] ~ {
ScalarMultiply: PUBLIC PROC [scalar: REF, in: ExtensionFieldElement, extensionField: AC.Structure] RETURNS [out: ExtensionFieldElement] ~ {
scalarPoly: ExtensionFieldElement ← POL.UnivariateMonomialConstructor[scalar, 0];
RETURN[Multiply[scalarPoly, in, extensionField] ];
};
Miscellaneous
Equal: PUBLIC PROC [in1, in2: ExtensionFieldElement, groundField: AC.Structure] RETURNS [BOOL] ~ {
RETURN[POL.Equal[in1, in2, groundField] ];
};
END.