\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra ffcat.spad}
\author{Johannes Grabmeier, Alfred Scheerhorn, Barry Trager, James Davenport}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\begin{verbatim}
-- 28.01.93: AS and JG:another Error in discreteLog(.,.) in FFIEDLC corrected.
-- 08.05.92: AS Error in discreteLog(.,.) in FFIEDLC corrected.
-- 03.04.92: AS Barry Trager added package FFSLPE and some functions to FFIELDC
-- 25.02.92: AS added following functions in FAXF: impl.of mrepresents,
-- linearAssociatedExp,linearAssociatedLog, linearAssociatedOrder
-- 18.02.92: AS: more efficient version of degree added,
-- first version of degree in FAXF set into comments
-- 18.06.91: AS: general version of minimalPolynomial added
-- 08.05.91: JG, AS implementation of missing functions in FFC and FAXF
-- 04.05.91: JG: comments
-- 04.04.91: JG: old version of charthRoot in FFC was dropped
-- Fields with finite characteristic
\end{verbatim}
\section{category FPC FieldOfPrimeCharacteristic}
<<category FPC FieldOfPrimeCharacteristic>>=
)abbrev category FPC FieldOfPrimeCharacteristic
++ Author: J. Grabmeier, A. Scheerhorn
++ Date Created: 10 March 1991
++ Date Last Updated: 31 March 1991
++ Basic Operations: _+, _*
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: field, finite field, prime characteristic
++ References:
++ J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++ AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++ FieldOfPrimeCharacteristic is the category of fields of prime
++ characteristic, e.g. finite fields, algebraic closures of
++ fields of prime characteristic, transcendental extensions of
++ of fields of prime characteristic.
FieldOfPrimeCharacteristic:Category == _
Join(Field,CharacteristicNonZero) with
order: $ -> OnePointCompletion PositiveInteger
++ order(a) computes the order of an element in the multiplicative
++ group of the field.
++ Error: if \spad{a} is 0.
discreteLog: ($,$) -> Union(NonNegativeInteger,"failed")
++ discreteLog(b,a) computes s with \spad{b**s = a} if such an s exists.
primeFrobenius: $ -> $
++ primeFrobenius(a) returns \spad{a ** p} where p is the characteristic.
primeFrobenius: ($,NonNegativeInteger) -> $
++ primeFrobenius(a,s) returns \spad{a**(p**s)} where p
++ is the characteristic.
add
primeFrobenius(a) == a ** characteristic()
primeFrobenius(a,s) == a ** (characteristic()**s)
@
\section{category XF ExtensionField}
<<category XF ExtensionField>>=
)abbrev category XF ExtensionField
++ Author: J. Grabmeier, A. Scheerhorn
++ Date Created: 10 March 1991
++ Date Last Updated: 31 March 1991
++ Basic Operations: _+, _*, extensionDegree, algebraic?, transcendent?
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: field, extension field
++ References:
++ J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++ AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++ ExtensionField {\em F} is the category of fields which extend
++ the field F
ExtensionField(F:Field) : Category == Join(Field,RetractableTo F,VectorSpace F) with
if F has CharacteristicZero then CharacteristicZero
if F has CharacteristicNonZero then FieldOfPrimeCharacteristic
algebraic? : $ -> Boolean
++ algebraic?(a) tests whether an element \spad{a} is algebraic with
++ respect to the ground field F.
transcendent? : $ -> Boolean
++ transcendent?(a) tests whether an element \spad{a} is transcendent
++ with respect to the ground field F.
inGroundField?: $ -> Boolean
++ inGroundField?(a) tests whether an element \spad{a}
++ is already in the ground field F.
degree : $ -> OnePointCompletion PositiveInteger
++ degree(a) returns the degree of minimal polynomial of an element
++ \spad{a} if \spad{a} is algebraic
++ with respect to the ground field F, and \spad{infinity} otherwise.
extensionDegree : () -> OnePointCompletion PositiveInteger
++ extensionDegree() returns the degree of the field extension if the
++ extension is algebraic, and \spad{infinity} if it is not.
transcendenceDegree : () -> NonNegativeInteger
++ transcendenceDegree() returns the transcendence degree of the
++ field extension, 0 if the extension is algebraic.
-- perhaps more absolute degree functions
if F has Finite then
FieldOfPrimeCharacteristic
Frobenius: $ -> $
++ Frobenius(a) returns \spad{a ** q} where q is the \spad{size()$F}.
Frobenius: ($,NonNegativeInteger) -> $
++ Frobenius(a,s) returns \spad{a**(q**s)} where q is the size()$F.
add
algebraic?(a) == not infinite? (degree(a)@OnePointCompletion_
(PositiveInteger))$OnePointCompletion(PositiveInteger)
transcendent? a == infinite?(degree(a)@OnePointCompletion _
(PositiveInteger))$OnePointCompletion(PositiveInteger)
if F has Finite then
Frobenius(a) == a ** size()$F
Frobenius(a,s) == a ** (size()$F ** s)
@
\section{category FAXF FiniteAlgebraicExtensionField}
<<category FAXF FiniteAlgebraicExtensionField>>=
)abbrev category FAXF FiniteAlgebraicExtensionField
++ Author: J. Grabmeier, A. Scheerhorn
++ Date Created: 11 March 1991
++ Date Last Updated: 31 March 1991
++ Basic Operations: _+, _*, extensionDegree,
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: field, extension field, algebraic extension, finite extension
++ References:
++ R.Lidl, H.Niederreiter: Finite Field, Encycoldia of Mathematics and
++ Its Applications, Vol. 20, Cambridge Univ. Press, 1983, ISBN 0 521 30240 4
++ J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++ AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++ FiniteAlgebraicExtensionField {\em F} is the category of fields
++ which are finite algebraic extensions of the field {\em F}.
++ If {\em F} is finite then any finite algebraic extension of {\em F} is finite, too.
++ Let {\em K} be a finite algebraic extension of the finite field {\em F}.
++ The exponentiation of elements of {\em K} defines a Z-module structure
++ on the multiplicative group of {\em K}. The additive group of {\em K}
++ becomes a module over the ring of polynomials over {\em F} via the operation
++ \spadfun{linearAssociatedExp}(a:K,f:SparseUnivariatePolynomial F)
++ which is linear over {\em F}, i.e. for elements {\em a} from {\em K},
++ {\em c,d} from {\em F} and {\em f,g} univariate polynomials over {\em F}
++ we have \spadfun{linearAssociatedExp}(a,cf+dg) equals {\em c} times
++ \spadfun{linearAssociatedExp}(a,f) plus {\em d} times
++ \spadfun{linearAssociatedExp}(a,g).
++ Therefore \spadfun{linearAssociatedExp} is defined completely by
++ its action on monomials from {\em F[X]}:
++ \spadfun{linearAssociatedExp}(a,monomial(1,k)\$SUP(F)) is defined to be
++ \spadfun{Frobenius}(a,k) which is {\em a**(q**k)} where {\em q=size()\$F}.
++ The operations order and discreteLog associated with the multiplicative
++ exponentiation have additive analogues associated to the operation
++ \spadfun{linearAssociatedExp}. These are the functions
++ \spadfun{linearAssociatedOrder} and \spadfun{linearAssociatedLog},
++ respectively.
FiniteAlgebraicExtensionField(F : Field) : Category == _
Join(ExtensionField F, RetractableTo F) with
-- should be unified with algebras
-- Join(ExtensionField F, FramedAlgebra F, RetractableTo F) with
basis : () -> Vector $
++ basis() returns a fixed basis of \$ as \spad{F}-vectorspace.
basis : PositiveInteger -> Vector $
++ basis(n) returns a fixed basis of a subfield of \$ as
++ \spad{F}-vectorspace.
coordinates : $ -> Vector F
++ coordinates(a) returns the coordinates of \spad{a} with respect
++ to the fixed \spad{F}-vectorspace basis.
coordinates : Vector $ -> Matrix F
++ coordinates([v1,...,vm]) returns the coordinates of the
++ vi's with to the fixed basis. The coordinates of vi are
++ contained in the ith row of the matrix returned by this
++ function.
represents: Vector F -> $
++ represents([a1,..,an]) returns \spad{a1*v1 + ... + an*vn}, where
++ v1,...,vn are the elements of the fixed basis.
minimalPolynomial: $ -> SparseUnivariatePolynomial F
++ minimalPolynomial(a) returns the minimal polynomial of an
++ element \spad{a} over the ground field F.
definingPolynomial: () -> SparseUnivariatePolynomial F
++ definingPolynomial() returns the polynomial used to define
++ the field extension.
extensionDegree : () -> PositiveInteger
++ extensionDegree() returns the degree of field extension.
degree : $ -> PositiveInteger
++ degree(a) returns the degree of the minimal polynomial of an
++ element \spad{a} over the ground field F.
norm: $ -> F
++ norm(a) computes the norm of \spad{a} with respect to the
++ field considered as an algebra with 1 over the ground field F.
trace: $ -> F
++ trace(a) computes the trace of \spad{a} with respect to
++ the field considered as an algebra with 1 over the ground field F.
if F has Finite then
FiniteFieldCategory
minimalPolynomial: ($,PositiveInteger) -> SparseUnivariatePolynomial $
++ minimalPolynomial(x,n) computes the minimal polynomial of x over
++ the field of extension degree n over the ground field F.
norm: ($,PositiveInteger) -> $
++ norm(a,d) computes the norm of \spad{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 \spad{a}.
++ Note: norm(a,d) = reduce(*,[a**(q**(d*i)) for i in 0..n/d])
trace: ($,PositiveInteger) -> $
++ trace(a,d) computes the trace of \spad{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 \spad{a}.
++ Note: \spad{trace(a,d) = reduce(+,[a**(q**(d*i)) for i in 0..n/d])}.
createNormalElement: () -> $
++ createNormalElement() computes a normal element over the ground
++ field F, that is,
++ \spad{a**(q**i), 0 <= i < extensionDegree()} is an F-basis,
++ where \spad{q = size()\$F}.
++ Reference: Such an element exists Lidl/Niederreiter: Theorem 2.35.
normalElement: () -> $
++ normalElement() returns a element, normal over the ground field F,
++ i.e. \spad{a**(q**i), 0 <= i < extensionDegree()} is an F-basis,
++ where \spad{q = size()\$F}.
++ At the first call, the element is computed by
++ \spadfunFrom{createNormalElement}{FiniteAlgebraicExtensionField}
++ then cached in a global variable.
++ On subsequent calls, the element is retrieved by referencing the
++ global variable.
normal?: $ -> Boolean
++ normal?(a) tests whether the element \spad{a} is normal over the
++ ground field F, i.e.
++ \spad{a**(q**i), 0 <= i <= extensionDegree()-1} is an F-basis,
++ where \spad{q = size()\$F}.
++ Implementation according to Lidl/Niederreiter: Theorem 2.39.
generator: () -> $
++ generator() returns a root of the defining polynomial.
++ This element generates the field as an algebra over the ground field.
linearAssociatedExp:($,SparseUnivariatePolynomial F) -> $
++ linearAssociatedExp(a,f) is linear over {\em F}, i.e.
++ for elements {\em a} from {\em \$}, {\em c,d} form {\em F} and
++ {\em f,g} univariate polynomials over {\em F} we have
++ \spadfun{linearAssociatedExp}(a,cf+dg) equals {\em c} times
++ \spadfun{linearAssociatedExp}(a,f) plus {\em d} times
++ \spadfun{linearAssociatedExp}(a,g). Therefore
++ \spadfun{linearAssociatedExp} is defined completely by its action on
++ monomials from {\em F[X]}:
++ \spadfun{linearAssociatedExp}(a,monomial(1,k)\$SUP(F)) is defined to
++ be \spadfun{Frobenius}(a,k) which is {\em a**(q**k)},
++ where {\em q=size()\$F}.
linearAssociatedOrder: $ -> SparseUnivariatePolynomial F
++ linearAssociatedOrder(a) retruns the monic polynomial {\em g} of
++ least degree, such that \spadfun{linearAssociatedExp}(a,g) is 0.
linearAssociatedLog: $ -> SparseUnivariatePolynomial F
++ linearAssociatedLog(a) returns a polynomial {\em g}, such that
++ \spadfun{linearAssociatedExp}(normalElement(),g) equals {\em a}.
linearAssociatedLog: ($,$) -> Union(SparseUnivariatePolynomial F,"failed")
++ linearAssociatedLog(b,a) returns a polynomial {\em g}, such that the
++ \spadfun{linearAssociatedExp}(b,g) equals {\em a}.
++ If there is no such polynomial {\em g}, then
++ \spadfun{linearAssociatedLog} fails.
add
I ==> Integer
PI ==> PositiveInteger
NNI ==> NonNegativeInteger
SUP ==> SparseUnivariatePolynomial
DLP ==> DiscreteLogarithmPackage
represents(v) ==
a:$:=0
b:=basis()
for i in 1..extensionDegree()@PI repeat
a:=a+(v.i)*(b.i)
a
transcendenceDegree() == 0$NNI
dimension() == (#basis()) ::NonNegativeInteger::CardinalNumber
extensionDegree():OnePointCompletion(PositiveInteger) ==
(#basis()) :: PositiveInteger::OnePointCompletion(PositiveInteger)
degree(a):OnePointCompletion(PositiveInteger) ==
degree(a)@PI::OnePointCompletion(PositiveInteger)
coordinates(v:Vector $) ==
m := new(#v, extensionDegree(), 0)$Matrix(F)
for i in minIndex v .. maxIndex v for j in minRowIndex m .. repeat
setRow_!(m, j, coordinates qelt(v, i))
m
algebraic? a == true
transcendent? a == false
extensionDegree() == (#basis()) :: PositiveInteger
-- degree a == degree(minimalPolynomial a)$SUP(F) :: PI
trace a ==
b := basis()
abs : F := 0
for i in 1..#b repeat
abs := abs + coordinates(a*b.i).i
abs
norm a ==
b := basis()
m := new(#b,#b, 0)$Matrix(F)
for i in 1..#b repeat
setRow_!(m,i, coordinates(a*b.i))
determinant(m)
if F has Finite then
linearAssociatedExp(x,f) ==
erg:$:=0
y:=x
for i in 0..degree(f) repeat
erg:=erg + coefficient(f,i) * y
y:=Frobenius(y)
erg
linearAssociatedLog(b,x) ==
x=0 => 0
l:List List F:=[entries coordinates b]
a:$:=b
extdeg:NNI:=extensionDegree()@PI
for i in 2..extdeg repeat
a:=Frobenius(a)
l:=concat(l,entries coordinates a)$(List List F)
l:=concat(l,entries coordinates x)$(List List F)
m1:=rowEchelon transpose matrix(l)$(Matrix F)
v:=zero(extdeg)$(Vector F)
rown:I:=1
for i in 1..extdeg repeat
if qelt(m1,rown,i) = 1$F then
v.i:=qelt(m1,rown,extdeg+1)
rown:=rown+1
p:=+/[monomial(v.(i+1),i::NNI) for i in 0..(#v-1)]
p=0 =>
messagePrint("linearAssociatedLog: second argument not in_
group generated by first argument")$OutputForm
"failed"
p
linearAssociatedLog(x) == linearAssociatedLog(normalElement(),x) ::
SparseUnivariatePolynomial(F)
linearAssociatedOrder(x) ==
x=0 => 0
l:List List F:=[entries coordinates x]
a:$:=x
for i in 1..extensionDegree()@PI repeat
a:=Frobenius(a)
l:=concat(l,entries coordinates a)$(List List F)
v:=first nullSpace transpose matrix(l)$(Matrix F)
+/[monomial(v.(i+1),i::NNI) for i in 0..(#v-1)]
charthRoot(x):Union($,"failed") ==
(charthRoot(x)@$)::Union($,"failed")
-- norm(e) == norm(e,1) pretend F
-- trace(e) == trace(e,1) pretend F
minimalPolynomial(a,n) ==
extensionDegree()@PI rem n ~= 0 =>
error "minimalPolynomial: 2. argument must divide extension degree"
f:SUP $:=monomial(1,1)$(SUP $) - monomial(a,0)$(SUP $)
u:$:=Frobenius(a,n)
while not(u = a) repeat
f:=f * (monomial(1,1)$(SUP $) - monomial(u,0)$(SUP $))
u:=Frobenius(u,n)
f
norm(e,s) ==
qr := divide(extensionDegree(), s)
zero?(qr.remainder) =>
pow := (size()-1) quo (size()$F ** s - 1)
e ** (pow::NonNegativeInteger)
error "norm: second argument must divide degree of extension"
trace(e,s) ==
qr:=divide(extensionDegree(),s)
q:=size()$F
zero?(qr.remainder) =>
a:$:=0
for i in 0..qr.quotient-1 repeat
a:=a + e**(q**(s*i))
a
error "trace: second argument must divide degree of extension"
size() == size()$F ** extensionDegree()
createNormalElement() ==
characteristic() = size() => 1
res : $
for i in 1.. repeat
res := index(i :: PI)
not inGroundField? res =>
normal? res => return res
-- theorem: there exists a normal element, this theorem is
-- unknown to the compiler
res
normal?(x:$) ==
p:SUP $:=(monomial(1,extensionDegree()) - monomial(1,0))@(SUP $)
f:SUP $:= +/[monomial(Frobenius(x,i),i)$(SUP $) _
for i in 0..extensionDegree()-1]
gcd(p,f) = 1 => true
false
degree a ==
y:$:=Frobenius a
deg:PI:=1
while y~=a repeat
y := Frobenius(y)
deg:=deg+1
deg
@
\section{package DLP DiscreteLogarithmPackage}
<<package DLP DiscreteLogarithmPackage>>=
)abbrev package DLP DiscreteLogarithmPackage
++ Author: J. Grabmeier, A. Scheerhorn
++ Date Created: 12 March 1991
++ Date Last Updated: 31 March 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: discrete logarithm
++ References:
++ J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++ AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++ DiscreteLogarithmPackage implements help functions for discrete logarithms
++ in monoids using small cyclic groups.
DiscreteLogarithmPackage(M): public == private where
M : Join(Monoid,Finite) with
"**": (M,Integer) -> M
++ x ** n returns x raised to the integer power n
public ==> with
shanksDiscLogAlgorithm:(M,M,NonNegativeInteger)-> _
Union(NonNegativeInteger,"failed")
++ shanksDiscLogAlgorithm(b,a,p) computes s with \spad{b**s = a} for
++ assuming that \spad{a} and b are elements in a 'small' cyclic group of
++ order p by Shank's algorithm.
++ Note: this is a subroutine of the function \spadfun{discreteLog}.
I ==> Integer
PI ==> PositiveInteger
NNI ==> NonNegativeInteger
SUP ==> SparseUnivariatePolynomial
DLP ==> DiscreteLogarithmPackage
private ==> add
shanksDiscLogAlgorithm(logbase,c,p) ==
limit:Integer:= 30
-- for logarithms up to cyclic groups of order limit a full
-- logarithm table is computed
p < limit =>
a:M:=1
disclog:Integer:=0
found:Boolean:=false
for i in 0..p-1 while not found repeat
a = c =>
disclog:=i
found:=true
a:=a*logbase
not found =>
messagePrint("discreteLog: second argument not in cyclic group_
generated by first argument")$OutputForm
"failed"
disclog pretend NonNegativeInteger
l:Integer:=length(p)$Integer
if odd?(l)$Integer then n:Integer:= shift(p,-(l quo 2))
else n:Integer:= shift(1,(l quo 2))
a:M:=1
exptable : Table(PI,NNI) :=table()$Table(PI,NNI)
for i in (0::NNI)..(n-1)::NNI repeat
insert_!([lookup(a),i::NNI]$Record(key:PI,entry:NNI),_
exptable)$Table(PI,NNI)
a:=a*logbase
found := false
end := (p-1) quo n
disclog:Integer:=0
a := c
b := logbase ** (-n)
for i in 0..end while not found repeat
rho:= search(lookup(a),exptable)_
$Table(PositiveInteger,NNI)
rho case NNI =>
found := true
disclog:= n * i + rho pretend Integer
a := a * b
not found =>
messagePrint("discreteLog: second argument not in cyclic group_
generated by first argument")$OutputForm
"failed"
disclog pretend NonNegativeInteger
@
\section{category FFIELDC FiniteFieldCategory}
<<category FFIELDC FiniteFieldCategory>>=
)abbrev category FFIELDC FiniteFieldCategory
++ Author: J. Grabmeier, A. Scheerhorn
++ Date Created: 11 March 1991
++ Date Last Updated: 31 March 1991
++ Basic Operations: _+, _*, extensionDegree, order, primitiveElement
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: field, extension field, algebraic extension, finite field
++ Galois field
++ References:
++ D.Lipson, Elements of Algebra and Algebraic Computing, The
++ Benjamin/Cummings Publishing Company, Inc.-Menlo Park, California, 1981.
++ J. Grabmeier, A. Scheerhorn: Finite Fields in AXIOM.
++ AXIOM Technical Report Series, ATR/5 NP2522.
++ Description:
++ FiniteFieldCategory is the category of finite fields
FiniteFieldCategory() : Category ==_
Join(FieldOfPrimeCharacteristic,Finite,StepThrough,DifferentialRing) with
-- ,PolynomialFactorizationExplicit) with
charthRoot: $ -> $
++ charthRoot(a) takes the characteristic'th root of {\em a}.
++ Note: such a root is alway defined in finite fields.
conditionP: Matrix $ -> Union(Vector $,"failed")
++ conditionP(mat), given a matrix representing a homogeneous system
++ of equations, returns a vector whose characteristic'th powers
++ is a non-trivial solution, or "failed" if no such vector exists.
-- the reason for implementing the following function is that we
-- can implement the functions order, getGenerator and primitive? on
-- category level without computing the, may be time intensive,
-- factorization of size()-1 at every function call again.
factorsOfCyclicGroupSize:_
() -> List Record(factor:Integer,exponent:Integer)
++ factorsOfCyclicGroupSize() returns the factorization of size()-1
-- the reason for implementing the function tableForDiscreteLogarithm
-- is that we can implement the functions discreteLog and
-- shanksDiscLogAlgorithm on category level
-- computing the necessary exponentiation tables in the respective
-- domains once and for all
-- absoluteDegree : $ -> PositiveInteger
-- ++ degree of minimal polynomial, if algebraic with respect
-- ++ to the prime subfield
tableForDiscreteLogarithm: Integer -> _
Table(PositiveInteger,NonNegativeInteger)
++ tableForDiscreteLogarithm(a,n) returns a table of the discrete
++ logarithms of \spad{a**0} up to \spad{a**(n-1)} which, called with
++ key \spad{lookup(a**i)} returns i for i in \spad{0..n-1}.
++ Error: if not called for prime divisors of order of
++ multiplicative group.
createPrimitiveElement: () -> $
++ createPrimitiveElement() computes a generator of the (cyclic)
++ multiplicative group of the field.
-- RDJ: Are these next lines to be included?
-- we run through the field and test, algorithms which construct
-- elements of larger order were found to be too slow
primitiveElement: () -> $
++ primitiveElement() returns a primitive element stored in a global
++ variable in the domain.
++ At first call, the primitive element is computed
++ by calling \spadfun{createPrimitiveElement}.
primitive?: $ -> Boolean
++ primitive?(b) tests whether the element b is a generator of the
++ (cyclic) multiplicative group of the field, i.e. is a primitive
++ element.
++ Implementation Note: see ch.IX.1.3, th.2 in D. Lipson.
discreteLog: $ -> NonNegativeInteger
++ discreteLog(a) computes the discrete logarithm of \spad{a}
++ with respect to \spad{primitiveElement()} of the field.
order: $ -> PositiveInteger
++ order(b) computes the order of an element b in the multiplicative
++ group of the field.
++ Error: if b equals 0.
representationType: () -> Union("prime","polynomial","normal","cyclic")
++ representationType() returns the type of the representation, one of:
++ \spad{prime}, \spad{polynomial}, \spad{normal}, or \spad{cyclic}.
add
I ==> Integer
PI ==> PositiveInteger
NNI ==> NonNegativeInteger
SUP ==> SparseUnivariatePolynomial
DLP ==> DiscreteLogarithmPackage
-- exported functions
differentiate x == 0
init() == 0
nextItem(a) ==
zero?(a:=index(lookup(a)+1)) => "failed"
a
order(e):OnePointCompletion(PositiveInteger) ==
(order(e)@PI)::OnePointCompletion(PositiveInteger)
conditionP(mat:Matrix $) ==
l:=nullSpace mat
empty? l or every?(zero?, first l) => "failed"
map(charthRoot,first l)
charthRoot(x:$):$ == x**(size() quo characteristic())
charthRoot(x:%):Union($,"failed") ==
(charthRoot(x)@$)::Union($,"failed")
createPrimitiveElement() ==
sm1 : PositiveInteger := (size()$$-1) pretend PositiveInteger
start : Integer :=
-- in the polynomial case, index from 1 to characteristic-1
-- gives prime field elements
representationType = "polynomial" => characteristic()::Integer
1
found : Boolean := false
for i in start.. while not found repeat
e : $ := index(i::PositiveInteger)
found := (order(e) = sm1)
e
primitive? a ==
-- add special implementation for prime field case
zero?(a) => false
explist := factorsOfCyclicGroupSize()
q:=(size()-1)@Integer
equalone : Boolean := false
for exp in explist while not equalone repeat
-- equalone := one?(a**(q quo exp.factor))
equalone := ((a**(q quo exp.factor)) = 1)
not equalone
order e ==
e = 0 => error "order(0) is not defined "
ord:Integer:= size()-1 -- order e divides ord
a:Integer:= 0
lof:=factorsOfCyclicGroupSize()
for rec in lof repeat -- run through prime divisors
a := ord quo (primeDivisor := rec.factor)
-- goon := one?(e**a)
goon := ((e**a) = 1)
-- run through exponents of the prime divisors
for j in 0..(rec.exponent)-2 while goon repeat
-- as long as we get (e**ord = 1) we
-- continue dividing by primeDivisor
ord := a
a := ord quo primeDivisor
-- goon := one?(e**a)
goon := ((e**a) = 1)
if goon then ord := a
-- as we do a top down search we have found the
-- correct exponent of primeDivisor in order e
-- and continue with next prime divisor
ord pretend PositiveInteger
discreteLog(b) ==
zero?(b) => error "discreteLog: logarithm of zero"
faclist:=factorsOfCyclicGroupSize()
a:=b
gen:=primitiveElement()
-- in GF(2) its necessary to have discreteLog(1) = 1
b = gen => 1
disclog:Integer:=0
mult:Integer:=1
groupord := (size() - 1)@Integer
exp:Integer:=groupord
for f in faclist repeat
fac:=f.factor
for t in 0..f.exponent-1 repeat
exp:=exp quo fac
-- shanks discrete logarithm algorithm
exptable:=tableForDiscreteLogarithm(fac)
n:=#exptable
c:=a**exp
end:=(fac - 1) quo n
found:=false
disc1:Integer:=0
for i in 0..end while not found repeat
rho:= search(lookup(c),exptable)_
$Table(PositiveInteger,NNI)
rho case NNI =>
found := true
disc1:=((n * i + rho)@Integer) * mult
c:=c* gen**((groupord quo fac) * (-n))
not found => error "discreteLog: ?? discrete logarithm"
-- end of shanks discrete logarithm algorithm
mult := mult * fac
disclog:=disclog+disc1
a:=a * (gen ** (-disc1))
disclog pretend NonNegativeInteger
discreteLog(logbase,b) ==
zero?(b) =>
messagePrint("discreteLog: logarithm of zero")$OutputForm
"failed"
zero?(logbase) =>
messagePrint("discreteLog: logarithm to base zero")$OutputForm
"failed"
b = logbase => 1
not zero?((groupord:=order(logbase)@PI) rem order(b)@PI) =>
messagePrint("discreteLog: second argument not in cyclic group _
generated by first argument")$OutputForm
"failed"
faclist:=factors factor groupord
a:=b
disclog:Integer:=0
mult:Integer:=1
exp:Integer:= groupord
for f in faclist repeat
fac:=f.factor
primroot:= logbase ** (groupord quo fac)
for t in 0..f.exponent-1 repeat
exp:=exp quo fac
rhoHelp:= shanksDiscLogAlgorithm(primroot,_
a**exp,fac pretend NonNegativeInteger)$DLP($)
rhoHelp case "failed" => return "failed"
rho := (rhoHelp :: NNI) * mult
disclog := disclog + rho
mult := mult * fac
a:=a * (logbase ** (-rho))
disclog pretend NonNegativeInteger
FP ==> SparseUnivariatePolynomial($)
FRP ==> Factored FP
f,g:FP
squareFreePolynomial(f:FP):FRP ==
squareFree(f)$UnivariatePolynomialSquareFree($,FP)
factorPolynomial(f:FP):FRP == factor(f)$DistinctDegreeFactorize($,FP)
factorSquareFreePolynomial(f:FP):FRP ==
f = 0 => 0
flist := distdfact(f,true)$DistinctDegreeFactorize($,FP)
(flist.cont :: FP) *
(*/[primeFactor(u.irr,u.pow) for u in flist.factors])
gcdPolynomial(f:FP,g:FP):FP ==
gcd(f,g)$EuclideanDomain_&(FP)
@
\section{FFIELDC.lsp BOOTSTRAP}
{\bf FFIELDC} depends on a chain of files. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf FFIELDC}
category which we can write into the {\bf MID} directory. We compile
the lisp code and copy the {\bf FFIELDC.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version.
Note that this code is not included in the generated catdef.spad file.
<<FFIELDC.lsp BOOTSTRAP>>=
(/VERSIONCHECK 2)
(DEFPARAMETER |FiniteFieldCategory;AL| 'NIL)
(DEFUN |FiniteFieldCategory| ()
(LET (#:G1395)
(COND
(|FiniteFieldCategory;AL|)
(T (SETQ |FiniteFieldCategory;AL| (|FiniteFieldCategory;|))))))
(DEFUN |FiniteFieldCategory;| ()
(PROG (#0=#:G1393)
(RETURN
(PROG1 (LETT #0#
(|Join| (|FieldOfPrimeCharacteristic|) (|Finite|)
(|StepThrough|) (|DifferentialRing|)
(|mkCategory| '|domain|
'(((|charthRoot| ($ $)) T)
((|conditionP|
((|Union| (|Vector| $) "failed")
(|Matrix| $)))
T)
((|factorsOfCyclicGroupSize|
((|List|
(|Record|
(|:| |factor| (|Integer|))
(|:| |exponent| (|Integer|))))))
T)
((|tableForDiscreteLogarithm|
((|Table| (|PositiveInteger|)
(|NonNegativeInteger|))
(|Integer|)))
T)
((|createPrimitiveElement| ($)) T)
((|primitiveElement| ($)) T)
((|primitive?| ((|Boolean|) $)) T)
((|discreteLog|
((|NonNegativeInteger|) $))
T)
((|order| ((|PositiveInteger|) $)) T)
((|representationType|
((|Union| "prime" "polynomial"
"normal" "cyclic")))
T))
NIL
'((|PositiveInteger|)
(|NonNegativeInteger|) (|Boolean|)
(|Table| (|PositiveInteger|)
(|NonNegativeInteger|))
(|Integer|)
(|List| (|Record|
(|:| |factor| (|Integer|))
(|:| |exponent| (|Integer|))))
(|Matrix| $))
NIL))
|FiniteFieldCategory|)
(SETELT #0# 0 '(|FiniteFieldCategory|))))))
(MAKEPROP '|FiniteFieldCategory| 'NILADIC T)
@
\section{FFIELDC-.lsp BOOTSTRAP}
{\bf FFIELDC-} depends on {\bf FFIELDC}. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf FFIELDC-}
category which we can write into the {\bf MID} directory. We compile
the lisp code and copy the {\bf FFIELDC-.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version.
Note that this code is not included in the generated catdef.spad file.
<<FFIELDC-.lsp BOOTSTRAP>>=
(/VERSIONCHECK 2)
(DEFUN |FFIELDC-;differentiate;2S;1| (|x| $) (|spadConstant| $ 7))
(DEFUN |FFIELDC-;init;S;2| ($) (|spadConstant| $ 7))
(DEFUN |FFIELDC-;nextItem;SU;3| (|a| $)
(COND
((SPADCALL
(LETT |a|
(SPADCALL (+ (SPADCALL |a| (|getShellEntry| $ 11)) 1)
(|getShellEntry| $ 12))
|FFIELDC-;nextItem;SU;3|)
(|getShellEntry| $ 14))
(CONS 1 "failed"))
('T (CONS 0 |a|))))
(DEFUN |FFIELDC-;order;SOpc;4| (|e| $)
(SPADCALL (SPADCALL |e| (|getShellEntry| $ 17))
(|getShellEntry| $ 20)))
(DEFUN |FFIELDC-;conditionP;MU;5| (|mat| $)
(PROG (|l|)
(RETURN
(SEQ (LETT |l| (SPADCALL |mat| (|getShellEntry| $ 25))
|FFIELDC-;conditionP;MU;5|)
(COND
((OR (NULL |l|)
(SPADCALL (ELT $ 14) (|SPADfirst| |l|)
(|getShellEntry| $ 27)))
(EXIT (CONS 1 "failed"))))
(EXIT (CONS 0
(SPADCALL (ELT $ 28) (|SPADfirst| |l|)
(|getShellEntry| $ 30))))))))
(DEFUN |FFIELDC-;charthRoot;2S;6| (|x| $)
(SPADCALL |x|
(QUOTIENT2 (SPADCALL (|getShellEntry| $ 36))
(SPADCALL (|getShellEntry| $ 37)))
(|getShellEntry| $ 38)))
(DEFUN |FFIELDC-;charthRoot;SU;7| (|x| $)
(CONS 0 (SPADCALL |x| (|getShellEntry| $ 28))))
(DEFUN |FFIELDC-;createPrimitiveElement;S;8| ($)
(PROG (|sm1| |start| |i| #0=#:G1441 |e| |found|)
(RETURN
(SEQ (LETT |sm1| (- (SPADCALL (|getShellEntry| $ 36)) 1)
|FFIELDC-;createPrimitiveElement;S;8|)
(LETT |start|
(COND
((SPADCALL (SPADCALL (|getShellEntry| $ 43))
(CONS 1 "polynomial") (|getShellEntry| $ 44))
(SPADCALL (|getShellEntry| $ 37)))
('T 1))
|FFIELDC-;createPrimitiveElement;S;8|)
(LETT |found| 'NIL |FFIELDC-;createPrimitiveElement;S;8|)
(SEQ (LETT |i| |start|
|FFIELDC-;createPrimitiveElement;S;8|)
G190
(COND
((NULL (SPADCALL |found| (|getShellEntry| $ 45)))
(GO G191)))
(SEQ (LETT |e|
(SPADCALL
(PROG1 (LETT #0# |i|
|FFIELDC-;createPrimitiveElement;S;8|)
(|check-subtype| (> #0# 0)
'(|PositiveInteger|) #0#))
(|getShellEntry| $ 12))
|FFIELDC-;createPrimitiveElement;S;8|)
(EXIT (LETT |found|
(EQL (SPADCALL |e|
(|getShellEntry| $ 17))
|sm1|)
|FFIELDC-;createPrimitiveElement;S;8|)))
(LETT |i| (+ |i| 1)
|FFIELDC-;createPrimitiveElement;S;8|)
(GO G190) G191 (EXIT NIL))
(EXIT |e|)))))
(DEFUN |FFIELDC-;primitive?;SB;9| (|a| $)
(PROG (|explist| |q| |exp| #0=#:G1453 |equalone|)
(RETURN
(SEQ (COND
((SPADCALL |a| (|getShellEntry| $ 14)) 'NIL)
('T
(SEQ (LETT |explist| (SPADCALL (|getShellEntry| $ 49))
|FFIELDC-;primitive?;SB;9|)
(LETT |q| (- (SPADCALL (|getShellEntry| $ 36)) 1)
|FFIELDC-;primitive?;SB;9|)
(LETT |equalone| 'NIL |FFIELDC-;primitive?;SB;9|)
(SEQ (LETT |exp| NIL |FFIELDC-;primitive?;SB;9|)
(LETT #0# |explist| |FFIELDC-;primitive?;SB;9|)
G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |exp| (CAR #0#)
|FFIELDC-;primitive?;SB;9|)
NIL)
(NULL (SPADCALL |equalone|
(|getShellEntry| $ 45))))
(GO G191)))
(SEQ (EXIT (LETT |equalone|
(SPADCALL
(SPADCALL |a|
(QUOTIENT2 |q| (QCAR |exp|))
(|getShellEntry| $ 50))
(|spadConstant| $ 41)
(|getShellEntry| $ 51))
|FFIELDC-;primitive?;SB;9|)))
(LETT #0# (CDR #0#) |FFIELDC-;primitive?;SB;9|)
(GO G190) G191 (EXIT NIL))
(EXIT (SPADCALL |equalone| (|getShellEntry| $ 45))))))))))
(DEFUN |FFIELDC-;order;SPi;10| (|e| $)
(PROG (|lof| |rec| #0=#:G1461 |primeDivisor| |j| #1=#:G1462 |a|
|goon| |ord|)
(RETURN
(SEQ (COND
((SPADCALL |e| (|spadConstant| $ 7)
(|getShellEntry| $ 51))
(|error| "order(0) is not defined "))
('T
(SEQ (LETT |ord| (- (SPADCALL (|getShellEntry| $ 36)) 1)
|FFIELDC-;order;SPi;10|)
(LETT |a| 0 |FFIELDC-;order;SPi;10|)
(LETT |lof| (SPADCALL (|getShellEntry| $ 49))
|FFIELDC-;order;SPi;10|)
(SEQ (LETT |rec| NIL |FFIELDC-;order;SPi;10|)
(LETT #0# |lof| |FFIELDC-;order;SPi;10|) G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |rec| (CAR #0#)
|FFIELDC-;order;SPi;10|)
NIL))
(GO G191)))
(SEQ (LETT |a|
(QUOTIENT2 |ord|
(LETT |primeDivisor| (QCAR |rec|)
|FFIELDC-;order;SPi;10|))
|FFIELDC-;order;SPi;10|)
(LETT |goon|
(SPADCALL
(SPADCALL |e| |a|
(|getShellEntry| $ 50))
(|spadConstant| $ 41)
(|getShellEntry| $ 51))
|FFIELDC-;order;SPi;10|)
(SEQ (LETT |j| 0 |FFIELDC-;order;SPi;10|)
(LETT #1# (- (QCDR |rec|) 2)
|FFIELDC-;order;SPi;10|)
G190
(COND
((OR (QSGREATERP |j| #1#)
(NULL |goon|))
(GO G191)))
(SEQ (LETT |ord| |a|
|FFIELDC-;order;SPi;10|)
(LETT |a|
(QUOTIENT2 |ord|
|primeDivisor|)
|FFIELDC-;order;SPi;10|)
(EXIT
(LETT |goon|
(SPADCALL
(SPADCALL |e| |a|
(|getShellEntry| $ 50))
(|spadConstant| $ 41)
(|getShellEntry| $ 51))
|FFIELDC-;order;SPi;10|)))
(LETT |j| (QSADD1 |j|)
|FFIELDC-;order;SPi;10|)
(GO G190) G191 (EXIT NIL))
(EXIT (COND
(|goon|
(LETT |ord| |a|
|FFIELDC-;order;SPi;10|)))))
(LETT #0# (CDR #0#) |FFIELDC-;order;SPi;10|)
(GO G190) G191 (EXIT NIL))
(EXIT |ord|))))))))
(DEFUN |FFIELDC-;discreteLog;SNni;11| (|b| $)
(PROG (|faclist| |gen| |groupord| |f| #0=#:G1482 |fac| |t| #1=#:G1483
|exp| |exptable| |n| |end| |i| |rho| |found| |disc1| |c|
|mult| |disclog| |a|)
(RETURN
(SEQ (COND
((SPADCALL |b| (|getShellEntry| $ 14))
(|error| "discreteLog: logarithm of zero"))
('T
(SEQ (LETT |faclist| (SPADCALL (|getShellEntry| $ 49))
|FFIELDC-;discreteLog;SNni;11|)
(LETT |a| |b| |FFIELDC-;discreteLog;SNni;11|)
(LETT |gen| (SPADCALL (|getShellEntry| $ 54))
|FFIELDC-;discreteLog;SNni;11|)
(EXIT (COND
((SPADCALL |b| |gen| (|getShellEntry| $ 51))
1)
('T
(SEQ (LETT |disclog| 0
|FFIELDC-;discreteLog;SNni;11|)
(LETT |mult| 1
|FFIELDC-;discreteLog;SNni;11|)
(LETT |groupord|
(-
(SPADCALL
(|getShellEntry| $ 36))
1)
|FFIELDC-;discreteLog;SNni;11|)
(LETT |exp| |groupord|
|FFIELDC-;discreteLog;SNni;11|)
(SEQ (LETT |f| NIL
|FFIELDC-;discreteLog;SNni;11|)
(LETT #0# |faclist|
|FFIELDC-;discreteLog;SNni;11|)
G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |f| (CAR #0#)
|FFIELDC-;discreteLog;SNni;11|)
NIL))
(GO G191)))
(SEQ
(LETT |fac| (QCAR |f|)
|FFIELDC-;discreteLog;SNni;11|)
(EXIT
(SEQ
(LETT |t| 0
|FFIELDC-;discreteLog;SNni;11|)
(LETT #1# (- (QCDR |f|) 1)
|FFIELDC-;discreteLog;SNni;11|)
G190
(COND
((QSGREATERP |t| #1#)
(GO G191)))
(SEQ
(LETT |exp|
(QUOTIENT2 |exp| |fac|)
|FFIELDC-;discreteLog;SNni;11|)
(LETT |exptable|
(SPADCALL |fac|
(|getShellEntry| $ 56))
|FFIELDC-;discreteLog;SNni;11|)
(LETT |n|
(SPADCALL |exptable|
(|getShellEntry| $ 57))
|FFIELDC-;discreteLog;SNni;11|)
(LETT |c|
(SPADCALL |a| |exp|
(|getShellEntry| $ 50))
|FFIELDC-;discreteLog;SNni;11|)
(LETT |end|
(QUOTIENT2 (- |fac| 1) |n|)
|FFIELDC-;discreteLog;SNni;11|)
(LETT |found| 'NIL
|FFIELDC-;discreteLog;SNni;11|)
(LETT |disc1| 0
|FFIELDC-;discreteLog;SNni;11|)
(SEQ
(LETT |i| 0
|FFIELDC-;discreteLog;SNni;11|)
G190
(COND
((OR
(QSGREATERP |i| |end|)
(NULL
(SPADCALL |found|
(|getShellEntry| $ 45))))
(GO G191)))
(SEQ
(LETT |rho|
(SPADCALL
(SPADCALL |c|
(|getShellEntry| $ 11))
|exptable|
(|getShellEntry| $ 59))
|FFIELDC-;discreteLog;SNni;11|)
(EXIT
(COND
((QEQCAR |rho| 0)
(SEQ
(LETT |found| 'T
|FFIELDC-;discreteLog;SNni;11|)
(EXIT
(LETT |disc1|
(*
(+ (* |n| |i|)
(QCDR |rho|))
|mult|)
|FFIELDC-;discreteLog;SNni;11|))))
('T
(LETT |c|
(SPADCALL |c|
(SPADCALL |gen|
(*
(QUOTIENT2
|groupord| |fac|)
(- |n|))
(|getShellEntry| $
50))
(|getShellEntry| $
60))
|FFIELDC-;discreteLog;SNni;11|)))))
(LETT |i| (QSADD1 |i|)
|FFIELDC-;discreteLog;SNni;11|)
(GO G190) G191 (EXIT NIL))
(EXIT
(COND
(|found|
(SEQ
(LETT |mult|
(* |mult| |fac|)
|FFIELDC-;discreteLog;SNni;11|)
(LETT |disclog|
(+ |disclog| |disc1|)
|FFIELDC-;discreteLog;SNni;11|)
(EXIT
(LETT |a|
(SPADCALL |a|
(SPADCALL |gen|
(- |disc1|)
(|getShellEntry| $
50))
(|getShellEntry| $
60))
|FFIELDC-;discreteLog;SNni;11|))))
('T
(|error|
"discreteLog: ?? discrete logarithm")))))
(LETT |t| (QSADD1 |t|)
|FFIELDC-;discreteLog;SNni;11|)
(GO G190) G191 (EXIT NIL))))
(LETT #0# (CDR #0#)
|FFIELDC-;discreteLog;SNni;11|)
(GO G190) G191 (EXIT NIL))
(EXIT |disclog|))))))))))))
(DEFUN |FFIELDC-;discreteLog;2SU;12| (|logbase| |b| $)
(PROG (|groupord| |faclist| |f| #0=#:G1501 |fac| |primroot| |t|
#1=#:G1502 |exp| |rhoHelp| #2=#:G1500 |rho| |disclog|
|mult| |a|)
(RETURN
(SEQ (EXIT (COND
((SPADCALL |b| (|getShellEntry| $ 14))
(SEQ (SPADCALL "discreteLog: logarithm of zero"
(|getShellEntry| $ 65))
(EXIT (CONS 1 "failed"))))
((SPADCALL |logbase| (|getShellEntry| $ 14))
(SEQ (SPADCALL
"discreteLog: logarithm to base zero"
(|getShellEntry| $ 65))
(EXIT (CONS 1 "failed"))))
((SPADCALL |b| |logbase| (|getShellEntry| $ 51))
(CONS 0 1))
('T
(COND
((NULL (ZEROP (REMAINDER2
(LETT |groupord|
(SPADCALL |logbase|
(|getShellEntry| $ 17))
|FFIELDC-;discreteLog;2SU;12|)
(SPADCALL |b|
(|getShellEntry| $ 17)))))
(SEQ (SPADCALL
"discreteLog: second argument not in cyclic group generated by first argument"
(|getShellEntry| $ 65))
(EXIT (CONS 1 "failed"))))
('T
(SEQ (LETT |faclist|
(SPADCALL
(SPADCALL |groupord|
(|getShellEntry| $ 67))
(|getShellEntry| $ 69))
|FFIELDC-;discreteLog;2SU;12|)
(LETT |a| |b|
|FFIELDC-;discreteLog;2SU;12|)
(LETT |disclog| 0
|FFIELDC-;discreteLog;2SU;12|)
(LETT |mult| 1
|FFIELDC-;discreteLog;2SU;12|)
(LETT |exp| |groupord|
|FFIELDC-;discreteLog;2SU;12|)
(SEQ (LETT |f| NIL
|FFIELDC-;discreteLog;2SU;12|)
(LETT #0# |faclist|
|FFIELDC-;discreteLog;2SU;12|)
G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |f| (CAR #0#)
|FFIELDC-;discreteLog;2SU;12|)
NIL))
(GO G191)))
(SEQ (LETT |fac| (QCAR |f|)
|FFIELDC-;discreteLog;2SU;12|)
(LETT |primroot|
(SPADCALL |logbase|
(QUOTIENT2 |groupord| |fac|)
(|getShellEntry| $ 50))
|FFIELDC-;discreteLog;2SU;12|)
(EXIT
(SEQ
(LETT |t| 0
|FFIELDC-;discreteLog;2SU;12|)
(LETT #1# (- (QCDR |f|) 1)
|FFIELDC-;discreteLog;2SU;12|)
G190
(COND
((QSGREATERP |t| #1#)
(GO G191)))
(SEQ
(LETT |exp|
(QUOTIENT2 |exp| |fac|)
|FFIELDC-;discreteLog;2SU;12|)
(LETT |rhoHelp|
(SPADCALL |primroot|
(SPADCALL |a| |exp|
(|getShellEntry| $ 50))
|fac|
(|getShellEntry| $ 71))
|FFIELDC-;discreteLog;2SU;12|)
(EXIT
(COND
((QEQCAR |rhoHelp| 1)
(PROGN
(LETT #2#
(CONS 1 "failed")
|FFIELDC-;discreteLog;2SU;12|)
(GO #2#)))
('T
(SEQ
(LETT |rho|
(* (QCDR |rhoHelp|)
|mult|)
|FFIELDC-;discreteLog;2SU;12|)
(LETT |disclog|
(+ |disclog| |rho|)
|FFIELDC-;discreteLog;2SU;12|)
(LETT |mult|
(* |mult| |fac|)
|FFIELDC-;discreteLog;2SU;12|)
(EXIT
(LETT |a|
(SPADCALL |a|
(SPADCALL |logbase|
(- |rho|)
(|getShellEntry| $
50))
(|getShellEntry| $ 60))
|FFIELDC-;discreteLog;2SU;12|)))))))
(LETT |t| (QSADD1 |t|)
|FFIELDC-;discreteLog;2SU;12|)
(GO G190) G191 (EXIT NIL))))
(LETT #0# (CDR #0#)
|FFIELDC-;discreteLog;2SU;12|)
(GO G190) G191 (EXIT NIL))
(EXIT (CONS 0 |disclog|))))))))
#2# (EXIT #2#)))))
(DEFUN |FFIELDC-;squareFreePolynomial| (|f| $)
(SPADCALL |f| (|getShellEntry| $ 76)))
(DEFUN |FFIELDC-;factorPolynomial| (|f| $)
(SPADCALL |f| (|getShellEntry| $ 78)))
(DEFUN |FFIELDC-;factorSquareFreePolynomial| (|f| $)
(PROG (|flist| |u| #0=#:G1515 #1=#:G1512 #2=#:G1510 #3=#:G1511)
(RETURN
(SEQ (COND
((SPADCALL |f| (|spadConstant| $ 79)
(|getShellEntry| $ 80))
(|spadConstant| $ 81))
('T
(SEQ (LETT |flist|
(SPADCALL |f| 'T (|getShellEntry| $ 85))
|FFIELDC-;factorSquareFreePolynomial|)
(EXIT (SPADCALL
(SPADCALL (QCAR |flist|)
(|getShellEntry| $ 86))
(PROGN
(LETT #3# NIL
|FFIELDC-;factorSquareFreePolynomial|)
(SEQ (LETT |u| NIL
|FFIELDC-;factorSquareFreePolynomial|)
(LETT #0# (QCDR |flist|)
|FFIELDC-;factorSquareFreePolynomial|)
G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |u| (CAR #0#)
|FFIELDC-;factorSquareFreePolynomial|)
NIL))
(GO G191)))
(SEQ
(EXIT
(PROGN
(LETT #1#
(SPADCALL (QCAR |u|)
(QCDR |u|)
(|getShellEntry| $ 87))
|FFIELDC-;factorSquareFreePolynomial|)
(COND
(#3#
(LETT #2#
(SPADCALL #2# #1#
(|getShellEntry| $ 88))
|FFIELDC-;factorSquareFreePolynomial|))
('T
(PROGN
(LETT #2# #1#
|FFIELDC-;factorSquareFreePolynomial|)
(LETT #3# 'T
|FFIELDC-;factorSquareFreePolynomial|)))))))
(LETT #0# (CDR #0#)
|FFIELDC-;factorSquareFreePolynomial|)
(GO G190) G191 (EXIT NIL))
(COND
(#3# #2#)
('T (|spadConstant| $ 89))))
(|getShellEntry| $ 90))))))))))
(DEFUN |FFIELDC-;gcdPolynomial;3Sup;16| (|f| |g| $)
(SPADCALL |f| |g| (|getShellEntry| $ 92)))
(DEFUN |FiniteFieldCategory&| (|#1|)
(PROG (|dv$1| |dv$| $ |pv$|)
(RETURN
(PROGN
(LETT |dv$1| (|devaluate| |#1|) . #0=(|FiniteFieldCategory&|))
(LETT |dv$| (LIST '|FiniteFieldCategory&| |dv$1|) . #0#)
(LETT $ (|newShell| 95) . #0#)
(|setShellEntry| $ 0 |dv$|)
(|setShellEntry| $ 3
(LETT |pv$| (|buildPredVector| 0 0 NIL) . #0#))
(|stuffDomainSlots| $)
(|setShellEntry| $ 6 |#1|)
$))))
(MAKEPROP '|FiniteFieldCategory&| '|infovec|
(LIST '#(NIL NIL NIL NIL NIL NIL (|local| |#1|) (0 . |Zero|)
|FFIELDC-;differentiate;2S;1| |FFIELDC-;init;S;2|
(|PositiveInteger|) (4 . |lookup|) (9 . |index|)
(|Boolean|) (14 . |zero?|) (|Union| $ '"failed")
|FFIELDC-;nextItem;SU;3| (19 . |order|) (|Integer|)
(|OnePointCompletion| 10) (24 . |coerce|)
|FFIELDC-;order;SOpc;4| (|Vector| 6) (|List| 22)
(|Matrix| 6) (29 . |nullSpace|) (|Mapping| 13 6)
(34 . |every?|) (40 . |charthRoot|) (|Mapping| 6 6)
(45 . |map|) (|Vector| $) (|Union| 31 '"failed")
(|Matrix| $) |FFIELDC-;conditionP;MU;5|
(|NonNegativeInteger|) (51 . |size|)
(55 . |characteristic|) (59 . **)
|FFIELDC-;charthRoot;2S;6| |FFIELDC-;charthRoot;SU;7|
(65 . |One|)
(|Union| '"prime" '"polynomial" '"normal" '"cyclic")
(69 . |representationType|) (73 . =) (79 . |not|)
|FFIELDC-;createPrimitiveElement;S;8|
(|Record| (|:| |factor| 18) (|:| |exponent| 18))
(|List| 47) (84 . |factorsOfCyclicGroupSize|) (88 . **)
(94 . =) |FFIELDC-;primitive?;SB;9|
|FFIELDC-;order;SPi;10| (100 . |primitiveElement|)
(|Table| 10 35) (104 . |tableForDiscreteLogarithm|)
(109 . |#|) (|Union| 35 '"failed") (114 . |search|)
(120 . *) |FFIELDC-;discreteLog;SNni;11| (|Void|)
(|String|) (|OutputForm|) (126 . |messagePrint|)
(|Factored| $) (131 . |factor|) (|Factored| 18)
(136 . |factors|) (|DiscreteLogarithmPackage| 6)
(141 . |shanksDiscLogAlgorithm|)
|FFIELDC-;discreteLog;2SU;12|
(|SparseUnivariatePolynomial| 6) (|Factored| 73)
(|UnivariatePolynomialSquareFree| 6 73)
(148 . |squareFree|) (|DistinctDegreeFactorize| 6 73)
(153 . |factor|) (158 . |Zero|) (162 . =) (168 . |Zero|)
(|Record| (|:| |irr| 73) (|:| |pow| 18)) (|List| 82)
(|Record| (|:| |cont| 6) (|:| |factors| 83))
(172 . |distdfact|) (178 . |coerce|) (183 . |primeFactor|)
(189 . *) (195 . |One|) (199 . *) (|EuclideanDomain&| 73)
(205 . |gcd|) (|SparseUnivariatePolynomial| $)
|FFIELDC-;gcdPolynomial;3Sup;16|)
'#(|primitive?| 211 |order| 216 |nextItem| 226 |init| 231
|gcdPolynomial| 235 |discreteLog| 241 |differentiate| 252
|createPrimitiveElement| 257 |conditionP| 261 |charthRoot|
266)
'NIL
(CONS (|makeByteWordVec2| 1 'NIL)
(CONS '#()
(CONS '#()
(|makeByteWordVec2| 94
'(0 6 0 7 1 6 10 0 11 1 6 0 10 12 1 6
13 0 14 1 6 10 0 17 1 19 0 18 20 1 24
23 0 25 2 22 13 26 0 27 1 6 0 0 28 2
22 0 29 0 30 0 6 35 36 0 6 35 37 2 6
0 0 35 38 0 6 0 41 0 6 42 43 2 42 13
0 0 44 1 13 0 0 45 0 6 48 49 2 6 0 0
18 50 2 6 13 0 0 51 0 6 0 54 1 6 55
18 56 1 55 35 0 57 2 55 58 10 0 59 2
6 0 0 0 60 1 64 62 63 65 1 18 66 0 67
1 68 48 0 69 3 70 58 6 6 35 71 1 75
74 73 76 1 77 74 73 78 0 73 0 79 2 73
13 0 0 80 0 74 0 81 2 77 84 73 13 85
1 73 0 6 86 2 74 0 73 18 87 2 74 0 0
0 88 0 74 0 89 2 74 0 73 0 90 2 91 0
0 0 92 1 0 13 0 52 1 0 10 0 53 1 0 19
0 21 1 0 15 0 16 0 0 0 9 2 0 93 93 93
94 1 0 35 0 61 2 0 58 0 0 72 1 0 0 0
8 0 0 0 46 1 0 32 33 34 1 0 0 0 39 1
0 15 0 40)))))
'|lookupComplete|))
@
\section{package FFSLPE FiniteFieldSolveLinearPolynomialEquation}
<<package FFSLPE FiniteFieldSolveLinearPolynomialEquation>>=
)abbrev package FFSLPE FiniteFieldSolveLinearPolynomialEquation
++ Author: Davenport
++ Date Created: 1991
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ This package solves linear diophantine equations for Bivariate polynomials
++ over finite fields
FiniteFieldSolveLinearPolynomialEquation(F:FiniteFieldCategory,
FP:UnivariatePolynomialCategory F,
FPP:UnivariatePolynomialCategory FP): with
solveLinearPolynomialEquation: (List FPP, FPP) -> Union(List FPP,"failed")
++ solveLinearPolynomialEquation([f1, ..., fn], g)
++ (where the fi are relatively prime to each other)
++ returns a list of ai such that
++ \spad{g/prod fi = sum ai/fi}
++ or returns "failed" if no such list of ai's exists.
== add
oldlp:List FPP := []
slpePrime: FP := monomial(1,1)
oldtable:Vector List FPP := []
lp: List FPP
p: FPP
import DistinctDegreeFactorize(F,FP)
solveLinearPolynomialEquation(lp,p) ==
if (oldlp ~= lp) then
-- we have to generate a new table
deg:= +/[degree u for u in lp]
ans:Union(Vector List FPP,"failed"):="failed"
slpePrime:=monomial(1,1)+monomial(1,0) -- x+1: our starting guess
while (ans case "failed") repeat
ans:=tablePow(deg,slpePrime,lp)$GenExEuclid(FP,FPP)
if (ans case "failed") then
slpePrime:= nextItem(slpePrime)::FP
while (degree slpePrime > 1) and
not irreducible? slpePrime repeat
slpePrime := nextItem(slpePrime)::FP
oldtable:=(ans:: Vector List FPP)
answer:=solveid(p,slpePrime,oldtable)
answer
@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
-- - Redistributions of source code must retain the above copyright
-- notice, this list of conditions and the following disclaimer.
--
-- - Redistributions in binary form must reproduce the above copyright
-- notice, this list of conditions and the following disclaimer in
-- the documentation and/or other materials provided with the
-- distribution.
--
-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the
-- names of its contributors may be used to endorse or promote products
-- derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>
<<package DLP DiscreteLogarithmPackage>>
<<category FPC FieldOfPrimeCharacteristic>>
<<category XF ExtensionField>>
<<category FAXF FiniteAlgebraicExtensionField>>
<<category FFIELDC FiniteFieldCategory>>
<<package FFSLPE FiniteFieldSolveLinearPolynomialEquation>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}