\documentclass{article} \usepackage{open-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} <>= )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} <>= )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} <>= import Boolean import NonNegativeInteger import PositiveInteger import Vector import Matrix import SparseUnivariatePolynomial import OnePointCompletion import CardinalNumber )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(): PositiveInteger == (#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): Maybe % == just(charthRoot(x)@%) -- 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: %): PositiveInteger == y:$:=Frobenius a deg:PI:=1 while y~=a repeat y := Frobenius(y) deg:=deg+1 deg @ \section{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} <>= import Boolean import Integer import NonNegativeInteger import PositiveInteger import Matrix import List import Table import OnePointCompletion import SparseUnivariatePolynomial )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 == a := index(lookup(a)+1) zero? a => nothing just 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:%): Maybe % == just(charthRoot(x)@%) 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$% 1 found : Boolean := false e : $ 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)) not equalone order(e: %): PositiveInteger == e = 0 => error "order(0) is not defined " ord:Integer:= size()$%-1 -- order e divides ord lof:=factorsOfCyclicGroupSize() for rec in lof repeat -- run through prime divisors a := ord quo (primeDivisor := rec.factor) goon := one?(e**a) -- 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) 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{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} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. --Copyright (C) 2007-2010, Gabriel Dos Reis. --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. @ <<*>>= <> <> <> <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}