--* From postmaster%watson.vnet.ibm.com@yktvmv.watson.ibm.com Tue Aug 24 10:31:40 1993 --* Received: from yktvmv2.watson.ibm.com by radical.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA20508; Tue, 24 Aug 1993 10:31:40 -0400 --* X-External-Networks: yes --* Received: from watson.vnet.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 6079; Tue, 24 Aug 93 10:35:31 EDT --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Tue, 24 Aug 93 10:35:31 -0400 --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 0207; Tue, 24 Aug 1993 10:35:30 EDT --* Received: from matthew.watson.ibm.com by yktvmv.watson.ibm.com --* (IBM VM SMTP V2R3) with TCP; Tue, 24 Aug 93 10:35:29 EDT --* Received: by matthew.watson.ibm.com (AIX 3.2/UCB 5.64/4.03) --* id AA18716; Tue, 24 Aug 1993 10:36:42 -0400 --* Date: Tue, 24 Aug 1993 10:36:42 -0400 --* From: gianni@matthew.watson.ibm.com --* Message-Id: <9308241436.AA18716@matthew.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: should have a meaning for List FFE(S) [bug2.as][30.0 (current)] --@ Fixed by: SMW Sat Oct 09 15:03:21 1993 --@ Tested by: n/a --@ Summary: Repaired by previous fixes #include "aslib.as" #library DemoLib "asdem" import DemoLib UnivariatePolynomialCategory(R: Ring): Category == PolynomialCategory(R, NonNegativeInteger) with coefficient: (%,NonNegativeInteger) -> R monicDivide : (%,%) -> Record(quotient : %, remainder : %) ^ : (%,NonNegativeInteger) -> % IntegralDomain:Category == Ring with macro Boolean == Bit B == Bit N == Integer I == Integer min(aa,bb) == if aa < bb then aa else bb one? aa == aa = 1 facFlags ==> 'nil, sqfr, irred, prime' FFE(S:BasicType): BasicType with bracket: (facFlags, S, Integer) -> % apply: (%, 'xpnt') -> Integer apply: (%, 'fctr') -> S apply: (%, 'flg') -> facFlags set!: (%, 'xpnt', Integer) -> Integer == add Rep ==> Record(flg:facFlags, fctr:S, xpnt:Integer) import Rep import S import Integer (f:%) = (g:%):Bit == rep(f).fctr = rep(g).fctr and rep(f).xpnt = rep(g).xpnt (f:%) ~= (g:%):Bit == not(f=g) apply(f:%, tag:'xpnt'):Integer == rep(f).xpnt apply(f:%, tag:'fctr'):S == rep(f).fctr apply(f:%, tag:'flg'):facFlags == rep(f).flg set!(f:%, tag:'xpnt', e:Integer):Integer == set!(rep(f),xpnt,e) set!(f:%, tag:'fctr', s:S):S == set!(rep(f),fctr,s) set!(f:%, tag:'flg', flag:facFlags):facFlags == set!(rep(f),flg,flag) [flag:facFlags, s:S, e:Integer]:% == per [flag,s,e] apply(p: Outport, l: %): Outport == import String import S import Integer p("ffe(fctr: ")(rep(l).fctr)(" xpnt: ")(rep(l).xpnt)(")") Factored(S: BasicType with 1:% ) : with makeFR: (S, List FFE(S)) -> % factorList: % -> List FFE(S) unit: % -> S apply: (Outport, %) -> Outport == add Rep ==> Record(unit:S, faclist:List FFE(S)) import Rep makeFR(u:S, lffe:List FFE(S)):% == per [u, lffe] factorList(x:%):List FFE(S) == apply(rep(x),faclist) unit(x:%):S == apply(rep(x),unit) apply(p:Outport, f:%): Outport == import String import S import List FFE(S) import FFE(S) import 'xpnt' import 'fctr' import I if unit(f) ~= 1 then p:=p(unit f) for fac in factorList f repeat p:=p(" ")((fac.fctr)@S) if fac.xpnt ~= 1@I then p:=p("^")((fac.xpnt)@I) p --% UnivariatePolynomialSquareFree +++ Author: Dave Barton, Barry Trager +++ Date Created: +++ Date Last Updated: +++ Basic Functions: squareFree, squareFreePart +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ This package provides for square-free decomposition of +++ univariate polynomials over arbitrary rings, i.e. +++ a partial factorization such that each factor is a product +++ of irreducibles with multiplicity one and the factors are +++ pairwise relatively prime. If the ring +++ has characteristic zero, the result is guaranteed to satisfy +++ this condition. If the ring is an infinite ring of +++ finite characteristic, then it may not be possible to decide when +++ polynomials contain factors which are pth powers. In this +++ case, the flag associated with that polynomial is set to "nil" +++ (meaning that that polynomials are not guaranteed to be square-free). UnivariatePolynomialSquareFree(RC:IntegralDomain,P :PC):C == T where fUnion ==> Enumeration (nil, sqfr, irred, prime) FF ==> Record(flg:fUnion, fctr:P, xpnt:Integer) PC ==> Join(UnivariatePolynomialCategory(RC),IntegralDomain) with gcd: (%,%) -> % ++ gcd(p,q) computes the greatest-common-divisor of p and q. C ==> with squareFree: P -> Factored(P) ++ squareFree(p) computes the square-free factorization of the ++ univariate polynomial p. Each factor has no repeated roots, and the ++ factors are pairwise relatively prime. squareFreePart: P -> P ++ squareFreePart(p) returns a polynomial which has the same ++ irreducible factors as the univariate polynomial p, but each ++ factor has multiplicity one. BumInSepFFE: FF -> FF ++ BumInSepFFE(f) is a local function, exported only because ++ it has multiple conditional definitions. T ==> add -- if RC has CharacteristicZero then squareFreePart(p:P) : P == (p exquo gcd(p, differentiate p))::P -- else -- squareFreePart(p:P) == -- unit(s := squareFree(p)$%) * */[f.factor for f in factors s] -- if RC has FiniteFieldCategory then -- BumInSepFFE(ffe:FF) == -- [sqfr, map(charthRoot,ffe.fctr), characteristic$P*ffe.xpnt] -- else if RC has CharacteristicNonZero then -- BumInSepFFE(ffe:FF) == -- np := multiplyExponents(ffe.fctr,characteristic$P:NonNegativeInteger) -- (nthrp := charthRoot(np)) case failed => -- [nil, np, ffe.xpnt] -- [sqfr, nthrp, characteristic$P*ffe.xpnt] -- else -- BumInSepFFE(ffe:FF) == -- [nil, -- multiplyExponents(ffe.fctr,characteristic$P:NonNegativeInteger), -- ffe.xpnt] -- if RC has CharacteristicZero then squareFree(p:P) : Factored P == --Yun's algorithm - see SYMSAC '76, p.27 --Note ci primitive, so GCD's don't need to %do contents. --Change gcd to return cofctrs also? ci:=p; di:=differentiate(p); pi:=gcd(ci,di) zero?(degree pi) => (u,c,a):=unitNormal(p) makeFR(u,[[sqfr,c,1]]) i:NonNegativeInteger:=0; lffe:List FF:=[] while ~zero?(degree ci) repeat ci:=(ci exquo pi)::P di:=(di exquo pi)::P - differentiate(ci) pi:=gcd(ci,di) i:=i+1 degree(pi) > 0 => p:=(p exquo (pi^i))::P -- lffe:=[[sqfr,pi,i],:lffe] lffe:=cons([sqfr,pi,i],lffe) makeFR(p,lffe) -- else -- squareFree(p:P) == --Musser's algorithm - see SYMSAC '76, p.27 --p MUST BE PRIMITIVE, Any characteristic. --Note ci primitive, so GCD's don't need to %do contents. --Change gcd to return cofctrs also? -- ci := gcd(p,differentiate(p)) -- degree(ci)=0 => -- (u,c,a):=unitNormal(p) -- makeFR(u,[[sqfr,c,1]]) -- di := (p exquo ci)::P -- i:NonNegativeInteger:=0; lffe:List FF:=[] -- until degree(di)=0 repeat -- diprev := di -- di := gcd(ci,di) -- ci:=(ci exquo di)::P -- pi:=(diprev exquo di)::P -- i:=i+1 -- degree(pi) > 0 => -- p:=(p exquo pi**i)::P -- lffe:=[[sqfr,pi,i],:lffe] -- degree(p)=0 => makeFR(p,lffe) -- redSqfr:=squareFree(divideExponents(p,characteristic$P)::P) -- lsnil:= [BumInSepFFE(ffe) for ffe in factorList redSqfr] -- lffe:=append(lsnil,lffe) -- makeFR(unit redSqfr,lffe)