ExtensionFieldsImpl.mesa
Last Edited by: Arnon, June 10, 1985 4:19:22 pm PDT
DIRECTORY
Rope,
Basics,
Ascii,
IO,
AlgebraClasses,
MathConstructors,
RatIntervals,
Variables,
DistribPolys,
Polynomials,
AlgebraicNumbers,
ExtensionFields;
ExtensionFieldsImpl: CEDAR PROGRAM
IMPORTS Rope, IO, AlgebraClasses, RatIntervals, DistribPolys, Polynomials , MathConstructors
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];
primitiveElement: AC.Object ← data.primitiveElement;
primitiveElementData: AN.AlgebraicNumberData ← NARROW[primitiveElement.data];
fieldOfAlgebraicNumbersData: AN.FieldOfAlgebraicNumbersData ← NARROW[primitiveElement.structure.instanceData];
minPolyRing: AC.Structure ← fieldOfAlgebraicNumbersData.minPolyRing;
IF NOT fieldOfAlgebraicNumbersData.real THEN
RETURN[Rope.Cat[
"Extension of ",
data.groundField.class.printName[data.groundField],
" by root of ",
minPolyRing.class.toRope[primitiveElementData.minimalPolynomial]
] ]
ELSE {
out: Rope.ROPE ← Rope.Cat[
"Extension of ",
data.groundField.class.printName[data.groundField],
" by the unique root of ",
minPolyRing.class.toRope[primitiveElementData.minimalPolynomial]
];
out ← Rope.Cat[out, " in ", RI.RatIntervals.class.toRope[primitiveElementData.isolatingInterval] ];
RETURN[out];
};
};
ClassShortPrintName: AC.PrintNameProc = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
primitiveElement: AC.Object ← data.primitiveElement;
RETURN[Rope.Concat[
data.groundField.class.shortPrintName[data.groundField],
primitiveElement.structure.class.toRope[primitiveElement]
] ];
};
ClassCharacteristic: AC.StructureRankOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
RETURN[ primitiveElementData.minimalPolynomial.structure.class.characteristic[primitiveElementData.minimalPolynomial.structure] ]
};
ClassIsElementOf: AC.ElementOfProc = {
Assumes that if item is a ExtensionFieldElement, then it really belongs to the domain pointed to by its structure field.
fieldElement: ExtensionFieldElement;
IF NOT ISTYPE[item, ExtensionFieldElement] THEN RETURN[FALSE];
fieldElement ← NARROW[item];
IF NOT structure.class.structureEqual[structure, fieldElement.structure] THEN RETURN[FALSE];
RETURN[ TRUE ]
};
ClassLegalFirstChar: AC.LegalFirstCharOp = {
SELECT char FROM
'[, '( => RETURN[TRUE];
ENDCASE;
RETURN[FALSE];
};
ClassRead: AC.ReadOp = {
RETURN[ReadExtensionFieldElement[in, structure, FALSE] ];
};
ClassFromRope: AC.FromRopeOp = {
stream: IO.STREAM ← IO.RIS[in];
RETURN[ ClassRead[stream, structure] ];
};
ClassToExpr: AC.ToExprOp = {
data: ExtensionFieldData ← NARROW[in.structure.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
dummyObject: AC.Object ← NEW[AC.ObjectRec ← [structure: minPolyRing, data: in.data]];
out ← MathConstructors.MakeVector[1, LIST[POL.MakePolyExpr[dummyObject]], FALSE];
};
ClassZero: AC.NullaryOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
RETURN[ primitiveElementData.minimalPolynomial.structure.class.zero[primitiveElementData.minimalPolynomial.structure] ]
};
ClassOne: AC.NullaryOp = {
data: ExtensionFieldData ← NARROW[structure.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
RETURN[ primitiveElementData.minimalPolynomial.structure.class.one[primitiveElementData.minimalPolynomial.structure] ]
};
generalExtensionFieldClass: PUBLIC AC.StructureClass ← NEW[AC.StructureClassRec ← [
category: divisionAlgebra,
printName: ClassPrintName,
shortPrintName: ClassShortPrintName,
structureEqual: AC.defaultStructureEqualityTest,
characteristic: ClassCharacteristic,
isElementOf: ClassIsElementOf,
legalFirstChar: ClassLegalFirstChar,
read: ClassRead,
fromRope: ClassFromRope,
toRope: ToRope,
write: Write,
toExpr: ClassToExpr,
toIndexRope: ToIndexRope,
add: Add,
negate: Negate,
subtract: Subtract,
zero: ClassZero,
multiply: Multiply,
invert: Invert,
divide: Divide,
one: ClassOne,
scalarMultiply: ScalarMultiply,
equal: Equal,
ordered: FALSE,
propList: NIL
] ];
realExtensionFieldClass: PUBLIC AC.StructureClass ← NEW[AC.StructureClassRec ← [
category: divisionAlgebra,
printName: ClassPrintName,
shortPrintName: ClassShortPrintName,
structureEqual: AC.defaultStructureEqualityTest,
characteristic: ClassCharacteristic,
isElementOf: ClassIsElementOf,
legalFirstChar: ClassLegalFirstChar,
read: ClassRead,
fromRope: ClassFromRope,
toRope: ToRope,
write: Write,
toExpr: ClassToExpr,
toIndexRope: ToIndexRope,
add: Add,
negate: Negate,
subtract: Subtract,
zero: ClassZero,
multiply: Multiply,
invert: Invert,
divide: Divide,
one: ClassOne,
scalarMultiply: ScalarMultiply,
equal: Equal,
ordered: FALSE, -- can't set to true until have sign, abs, compare procs
completeField: FALSE, -- correct assuming we have a proper subfield of the reals
realField: TRUE, -- correct assuming we are not adjoining a complex algebraic number
realClosedField: FALSE,
algebraicallyClosedField: FALSE,
propList: NIL
] ];
ExtensionField Constructors
MakeExtensionField: PUBLIC PROC [primitiveElement: AN.AlgebraicNumber] RETURNS [extensionField: AC.Structure] ~ {
primitiveElementData: AN.AlgebraicNumberData ← NARROW[primitiveElement.data];
data: POL.PolynomialRingData ← NARROW[primitiveElementData.minimalPolynomial.structure.instanceData];
groundField: AC.Structure ← data.coeffRing;
extensionFieldData: ExtensionFieldData ← NEW[ExtensionFieldDataRec ← [
groundField: groundField,
primitiveElement: primitiveElement
] ];
IF groundField.class.category#field AND groundField.class.category#divisionAlgebra THEN ERROR BadGroundField[groundField];
IF NOT groundField.class.realField THEN -- equivalent to: IF NOT primitiveElement.real
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.category#field AND structure.class.category#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.category#field AND structure.class.category#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.category#field AND structure.class.category#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, extensionField: AC.Structure, reduced: BOOL ← FALSE] RETURNS [out: ExtensionFieldElement] ~ {
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
char: CHAR;
dElt: DP.DPolynomial;
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
minPolyRingData: POL.PolynomialRingData ← NARROW[minPolyRing.instanceData];
fieldElementVariable: VARS.VariableSeq ← minPolyRingData.variable;
[]← 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, minPolyRingData.coeffRing, DP.RightBracketProc]; -- terminated by a right bracket
[] ← in.GetChar[]; -- remove right bracket
out ← POL.PolyFromDPoly[ dElt, minPolyRing];
IF NOT reduced THEN out ← POL.Remainder[out, primitiveElementData.minimalPolynomial];
out.structure ← extensionField; -- "lift" it from a polynomial to an extFieldElt
};
ExtensionFieldElementFromRope: PUBLIC PROC [in: Rope.ROPE, extensionField: AC.Structure, reduced: BOOL ← FALSE] RETURNS [out: ExtensionFieldElement] ~ {
out ← ReadExtensionFieldElement[IO.RIS[in], extensionField, reduced];
};
ToRope: PUBLIC AC.ToRopeOp ~ {
extensionField: AC.Structure ← in.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
in.structure ← minPolyRing; -- make it look like a polynomial
out ← Rope.Cat["[ ", minPolyRing.class.toRope[in], " ]" ];
in.structure ← extensionField; -- restore
};
ToIndexRope: PUBLIC AC.ToRopeOp ~ {
out ← "ExtensionFieldElement";
};
Write: PUBLIC AC.WriteOp ~ {
stream.PutRope[ ToRope[in] ]
};
Arithmetic
Add: PUBLIC AC.BinaryOp ~ {
extensionField: AC.Structure ← firstArg.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
firstArg.structure ← minPolyRing; -- make it look like a polynomial
secondArg.structure ← minPolyRing; -- make it look like a polynomial
result ← POL.Add[firstArg, secondArg];
result.structure ← extensionField; -- lift
firstArg.structure ← extensionField; -- restore
secondArg.structure ← extensionField; -- restore
RETURN[ result ];
};
Negate: PUBLIC AC.UnaryOp ~ {
extensionField: AC.Structure ← arg.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
arg.structure ← minPolyRing; -- make it look like a polynomial
result ← POL.Negate[arg];
result.structure ← extensionField; -- lift
arg.structure ← extensionField; -- restore
RETURN[ result ];
};
Subtract: PUBLIC AC.BinaryOp ~ {
extensionField: AC.Structure ← firstArg.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
firstArg.structure ← minPolyRing; -- make it look like a polynomial
secondArg.structure ← minPolyRing; -- make it look like a polynomial
result ← POL.Subtract[firstArg, secondArg];
result.structure ← extensionField; -- lift
firstArg.structure ← extensionField; -- restore
secondArg.structure ← extensionField; -- restore
RETURN[ result ];
};
Multiply: PUBLIC AC.BinaryOp ~ {
extensionField: AC.Structure ← firstArg.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
firstArg.structure ← minPolyRing; -- make it look like a polynomial
secondArg.structure ← minPolyRing; -- make it look like a polynomial
result ← POL.Remainder[POL.Multiply[firstArg, secondArg], primitiveElementData.minimalPolynomial];
result.structure ← extensionField; -- lift
firstArg.structure ← extensionField; -- restore
secondArg.structure ← extensionField; -- restore
RETURN[ result ];
};
Invert: PUBLIC AC.UnaryOp ~ {
Divide: PUBLIC AC.BinaryOp ~ {
ScalarMultiply: PUBLIC AC.BinaryOp ~ {
extensionField: AC.Structure ← secondArg.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
scalarPoly: POL.Polynomial ← POL.Monom[firstArg, NEW[CARDINAL ← 0], minPolyRing]; -- will check that scalar belongs to minPolyRing
secondArg.structure ← minPolyRing; -- make it look like a polynomial
result ← POL.Multiply[scalarPoly, secondArg];
result.structure ← extensionField; -- lift
secondArg.structure ← extensionField; -- restore
RETURN[ result ];
};
Miscellaneous
Equal: PUBLIC AC.EqualityOp ~ {
extensionField: AC.Structure ← firstArg.structure; -- save
data: ExtensionFieldData ← NARROW[extensionField.instanceData];
primitiveElementData: AN.AlgebraicNumberData ← NARROW[data.primitiveElement.data];
minPolyRing: AC.Structure ← primitiveElementData.minimalPolynomial.structure;
val: BOOL;
firstArg.structure ← minPolyRing; -- make it look like a polynomial
secondArg.structure ← minPolyRing; -- make it look like a polynomial
val ← POL.Equal[firstArg, secondArg];
firstArg.structure ← extensionField; -- restore
secondArg.structure ← extensionField; -- restore
RETURN[val];
};
END.