--* From BMT%WATSON.vnet.ibm.com@yktvmh.watson.ibm.com Thu Dec 30 11:35:08 1993 --* Received: from yktvmh.watson.ibm.com by leonardo.watson.ibm.com (AIX 3.2/UCB 5.64/4.03) --* id AA11748; Thu, 30 Dec 1993 11:35:08 -0500 --* Received: from watson.vnet.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 5603; Thu, 30 Dec 93 11:41:14 EST --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Thu, 30 Dec 93 11:41:14 -0500 --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 8477; Thu, 30 Dec 1993 11:41:12 EST --* Received: from cyst.watson.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with TCP; Thu, 30 Dec 93 11:41:11 EST --* Received: from spadserv.watson.ibm.com by cyst.watson.ibm.com (AIX 3.2/UCB 5.64/900528) --* id AA84025; Thu, 30 Dec 1993 11:41:04 -0500 --* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA30165; Thu, 30 Dec 1993 11:43:17 -0500 --* Date: Thu, 30 Dec 1993 11:43:17 -0500 --* From: bmt@spadserv.watson.ibm.com --* X-External-Networks: yes --* Message-Id: <9312301643.AA30165@spadserv.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: [4] compiler gives many copies of messages [bug3.as][33.4 (current)] --@ Fixed by: SSD Mon Jan 9 15:19:58 EST 1995 --@ Tested by: none --@ Summary: Compiler no longer gives many copies of messages. (r1-0-3) Missing EuclideanModularRing is the first major problem with compiling this file. #include "aslib.as" --Copyright The Numerical Algorithms Group Limited 1991. --)abb package MDDFACT ModularDistinctDegreeFactorizer --% ModularDistinctDegreeFactorizer +++ Author: Barry Trager +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ This package supports factorization and gcds +++ of univariate polynomials over the integers modulo different +++ primes. The inputs are given as polynomials over the integers +++ with the prime passed explicitly as an extra argument. UnivariatePolynomialCategory(R:Ring):Category == Ring with ModularDistinctDegreeFactorizer(U):C == T where default U : UnivariatePolynomialCategory(Integer) I ==> Integer NNI ==> NonNegativeInteger PI ==> PositiveInteger V ==> Vector L ==> List DDRecord ==> Record(factor:EMR,degree:I) UDDRecord ==> Record(factor:U,degree:I) DDList ==> L DDRecord UDDList ==> L UDDRecord C ==> with gcd:(U,U,I) -> U ++ gcd(f1,f2,p) computes the gcd of the univariate polynomials ++ f1 and f2 modulo the integer prime p. factor:(U,I) -> L U ++ factor(f1,p) returns the list of factors of the univariate ++ polynomial f1 modulo the integer prime p. ++ Error: if f1 is not square-free modulo p. ddFact:(U,I) -> UDDList ++ ddFact(f,p) computes a distinct degree factorization of the ++ polynomial f modulo the prime p, i.e. such that each factor ++ is a product of irreducibles of the same degrees. separateFactors:(UDDList,I) -> L U ++ separateFactors(ddl, p) refines the distinct degree factorization ++ produced by \spadfunFrom{ddFact}{ModularDistinctDegreeFactorizer} ++ to give a complete list of factors. exptMod:(U,I,U,I) -> U ++ exptMod(f,n,g,p) raises the univariate polynomial f to the nth ++ power modulo the polynomial g and the prime p. T ==> add reduction(u:U,p:I):U == zero? p => u map(positiveRemainder(#1,p),u) merge(p:I,q:I):Partial(I) == p = q => p p = 0 => q q = 0 => p failed modInverse(c:I,p:I):I == (extendedEuclidean(c,p,1)::Record(coef1:I,coef2:I)).coef1 exactquo(u:U,v:U,p:I):Partial(U) == invlcv:=modInverse(leadingCoefficient v,p) r:=monicDivide(u,reduction(invlcv*v,p)) reduction(r.remainder,p) ^=0 => failed reduction(invlcv*r.quotient,p) EMR ==> EuclideanModularRing(Integer,U,Integer, reduction,merge,exactquo) probSplit2:(EMR,EMR,I) -> Partial List EMR trace:(EMR,I,EMR) -> EMR ddfactor:EMR -> L EMR ddfact:EMR -> DDList sepFact1:DDRecord -> L EMR sepfact:DDList -> L EMR probSplit:(EMR,EMR,I) -> Partial L EMR makeMonic:EMR -> EMR exptmod:(EMR,I,EMR) -> EMR lc(u:EMR):I == leadingCoefficient(u::U) degree(u:EMR):I == degree(u::U) makeMonic(u:EMR):EMR == modInverse(lc(u),modulus(u)) * u default i:I exptmod(u1:EMR,i:I,u2:EMR):EMR == i < 0 => error("negative exponentiation not allowed for exptMod") ans:= 1$EMR while i > 0 repeat if odd?(i) then ans:= (ans * u1) rem u2 i:= i quo 2 u1:= (u1 * u1) rem u2 ans exptMod(a:U,i:I,b:U,q:I):U == ans:= exptmod(reduce(a,q),i,reduce(b,q)) ans::U ddfactor(u:EMR):L EMR == if (c:= lc(u)) ^= 1$I then u:= makeMonic(u) ans:= sepfact(ddfact(u)) cons(c::EMR,[makeMonic(f) for f in ans | degree(f) > 0]) gcd(u:U,v:U,q:I):U == gcd(reduce(u,q),reduce(v,q))::U factor(u:U,q:I):L U == v:= reduce(u,q) dv:= reduce(differentiate(u),q) degree gcd(v,dv) > 0 => error("Modular factor: polynomial must be squarefree") ans:= ddfactor v [f::U for f in ans] ddfact(u:EMR):DDList == p:=modulus u w:= reduce(monomial(1,1)$U,p) m:= w d:I:= 1 if (c:= lc(u)) ^= 1$I then u:= makeMonic u ans:DDList:= [] repeat w:= exptmod(w,p,u) g:= gcd(w - m,u) if degree g > 0 then g:= makeMonic(g) ans:= cons([g,d],ans) u:= (u quo g) degree(u) = 0 => return cons([c::EMR,0$I],ans) d:= d+1 d > (degree(u) pretend I quo 2) => return cons([c::EMR,0$I],cons([u,degree(u)],ans)) ddFact(u:U,q:I):UDDList == ans:= ddfact(reduce(u,q)) [[(dd.factor)::U,dd.degree]$UDDRecord for dd in ans]$UDDList sepfact(factList:DDList):L EMR == reduce(concat,[sepFact1(f) for f in factList]) separateFactors(uddList:UDDList,q:I):L U == ans:= sepfact [[reduce(udd.factor,q),udd.degree]$DDRecord for udd in uddList]$DDList [f::U for f in ans] sepFact1(f:DDRecord):L EMR == u:= f.factor p:=modulus u (d := f.degree) = 0 => [u] if (c:= lc(u)) ^= 1$I then u:= makeMonic(u) d = (du := degree(u)) => [u] ans:L EMR:= [] x:U:= monomial(1,1) -- for small primes find linear factors by exaustion d=1 and p < 1000 => for i in 0.. while du > 0 repeat if u(i::U) = 0 then ans := cons(reduce(x-(i::U),p),ans) du := du-1 ans y:= x s:I:= 0 md:= 2*d+1 stack:L EMR:= [u] while not null stack repeat t:= reduce(((s::U)+x),p) if not ((flist:= probSplit(first stack,t,d)) case "failed") then stack:= rest stack for fact in flist repeat f1:= makeMonic(fact) (df1:= degree(f1)) = 0 => nil df1 > d => stack:= cons(f1,stack) ans:= cons(f1,ans) s:= s+1 s = p => s:= 0 x:= x*y+y cons(c * first(ans),rest(ans)) probSplit(u:EMR,t:EMR,d:I):Partial L EMR == (p:=modulus(u)) = 2 => probSplit2(u,t,d) f1:= gcd(u,t) r:= ((p**(d:NNI)-1) quo 2) pretend NNI n:= exptmod(t,r,u) f2:= gcd(u,n + 1) (g:= f1 * f2) = 1 => "failed" g = u => "failed" [f1,f2,(u quo g)] probSplit2(u:EMR,t:EMR,d:I):Partial List EMR == f:= gcd(u,trace(t,d,u)) f = 1 => "failed" [1,f,u quo f] trace(t:EMR,d:I,u:EMR):EMR == p:=modulus(t) d:= d - 1 while d > 0 repeat t:= (t + exptmod(t,p,u)) rem u d:= d - 1 t