--* From BMT%WATSON.vnet.ibm.com@yktvmv.watson.ibm.com Thu Aug 25 01:18:20 1994 --* Received: from yktvmv-ob.watson.ibm.com by asharp.watson.ibm.com (AIX 3.2/UCB 5.64/930311) --* id AA22947; Thu, 25 Aug 1994 01:18:20 -0400 --* Received: from watson.vnet.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 3363; Thu, 25 Aug 94 01:18:23 EDT --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Thu, 25 Aug 94 01:18:23 -0400 --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 5467; Thu, 25 Aug 1994 01:18:22 EDT --* Received: from spadserv.watson.ibm.com by yktvmv.watson.ibm.com --* (IBM VM SMTP V2R3) with TCP; Thu, 25 Aug 94 01:18:21 EDT --* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA17900; Thu, 25 Aug 1994 01:18:27 -0400 --* Date: Thu, 25 Aug 1994 01:18:27 -0400 --* From: bmt@spadserv.watson.ibm.com --* X-External-Networks: yes --* Message-Id: <9408250518.AA17900@spadserv.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: [3] compiler gets segmentation violation --@ Fixed by: SSD Fri Apr 14 17:37:29 EDT 1995 --@ Tested by: none --@ Summary: No longer exhibits segmentation fault. -- Command line: asharp -O -Fasy -Faso -Flsp -laxiom -Mno-AS_W_WillObsolete -DAxiom -x ddfact.as -- Version: 0.36.5 -- Original bug file name: ddfact.as #include "axiom.as" DDFACT ==> DistinctDegreeFactorize; fUnion ==> Union(nil: 'nil',sqfr: 'sqfr',irred: 'irred',prime: 'prime'); FFE ==> Record(flg: Union(nil: 'nil',sqfr: 'sqfr',irred: 'irred',prime: 'prime'),fctr : FP,xpnt: Z); NNI ==> NonNegativeInteger; Z ==> Integer; fact ==> Record(deg: NNI,prod: FP); ParFact ==> Record(irr: FP,pow: Z); FinalFact ==> Record(cont: F,factors: List ParFact); +++ Package for the factorization of a univariate polynomial with coefficients in +++ a finite field. The algorithm used is the "distinct degree" algorithm of +++ Cantor-Zassenhaus, modified to use trace instead of the norm and a table for +++ computing Frobenius as suggested by Naudin and Quitte . DistinctDegreeFactorize(F:FiniteFieldCategory,FP:UnivariatePolynomialCategory F) : with { factor: FP -> Factored FP; ++ `factor(p)' produces the complete factorization of the ++ polynomial `p'. factorSquareFree: FP -> Factored FP; ++ factor(`p') produces the complete factorization of the square ++ free polynomial `p'. distdfact: (FP,Boolean) -> FinalFact; separateDegrees: FP -> List fact; separateFactors: List fact -> List FP; exptMod: (FP,NNI,FP) -> FP; trace2PowMod: (FP,NNI,FP) -> FP; tracePowMod: (FP,NNI,FP) -> FP; irreducible?: FP -> Boolean; ++ `irreducible?(p)' tests whether the polynomial `p' is ++ irreducible. } == add { import from FP; import from F; -- import from UnivariatePolynomialSquareFree(F,FP); import from ModMonic(F,FP); import from Boolean; import from NNI; import from PositiveInteger; import from Z; D == ModMonic(F,FP); import from D; default notSqFr:(FP,FP -> List FP) -> List ParFact; default ddffact:FP -> List FP; default ddffact1:(FP,Boolean) -> List fact; default ranpol:NNI -> FP; charF := characteristic()$F = 2@NonNegativeInteger; ranpol (d:NNI):FP == { import from SingleInteger; k1:NNI := 0; while k1 = 0 repeat k1 := random d; charF => { u := 0$FP; for j in 1$NNI..k1@NNI repeat u := u + monomial(random()$F,j); u; } u := monomial(1,k1); for j in 0$NNI..(k1::Integer - 1$Integer)::NNI repeat u := u + monomial(random()$F,j); u; } notSqFr(m:FP,appl:FP -> List FP):List ParFact == { import from Fraction Z; import from Factored FP; import from ParFact; factlist:List ParFact := empty(); local llf: List ( Record(flg: Union(nil:'nil',sqfr:'sqfr',irred:'irred',prime:'prime'), fctr: FP,xpnt: Z)); fln:List FP := empty(); if not ((lcm:F := leadingCoefficient m) = 1) then m := inv lcm * m; llf := factorList squareFree m; for lf in llf repeat { d1 := lf xpnt; pol := lf fctr; if not ((lcp := leadingCoefficient pol) = 1) then pol := inv lcp * pol; degree pol = 1 => factlist := cons([pol,d1]$ParFact,factlist); fln := appl pol; factlist := append([[pf,d1]$ParFact for pf in fln],factlist); } factlist; } exptMod(u:FP,k:NNI,v:FP):FP == (reduce(u)$D ^ k) pretend FP rem v; trace2PowMod(u:FP,k:NNI,v:FP):FP == { import from SingleInteger; uu := u; for i in 1$Integer..k::Integer repeat uu := (u + uu * uu) rem v; uu; } tracePowMod(u:FP,k:NNI,v:FP):FP == { import from SingleInteger; u1:D := reduce(u)$D; uu:D := u1; for i in 1$Integer..k::Integer repeat uu := u1 + frobenius uu; lift uu rem v; } normPowMod(u:FP,k:NNI,v:FP):FP == { import from SingleInteger; import from Fraction Z; u1:D := reduce(u)$D; uu:D := u1; for i in 1$Integer..k::Integer repeat uu := u1 * frobenius uu; lift uu rem v; } ddffact1(m:FP,testirr:Boolean):List fact == { import from Fraction Z; import from fact; p := size$F; dg:NNI := 0; ddfact:List fact := empty(); local k1:NNI; u := m; du := degree u; setPoly u; mon:FP := monomial(1,1); v := mon; for free k1 in 1$Integer.. while not (du quo 2@NonNegativeInteger < k1) repeat { v := lift frobenius reduce(v)$D; g := gcd(v - mon,u); dg := degree g; dg = 0 => iterate; if not (leadingCoefficient g = 1) then g := inv leadingCoefficient g * g; ddfact := cons([k1,g]$fact,ddfact); testirr => return ddfact; u := u quo g; du := degree u; du = 0 => return ddfact; setPoly u; } cons([du,u]$fact,ddfact); } irreducible? (m:FP):Boolean == { import from List fact; mf:fact := first ddffact1(m,true); degree m = mf deg; } separateDegrees (m:FP):List fact == ddffact1(m,false); separateFactors (distf:List fact):List FP == { import from List ParFact; import from Fraction Z; ddfact := distf; local n1:Z; p1 := size()$F; if charF then n1 := length (p1::Integer) - 1$Integer; local newaux,aux,ris: List FP; ris := empty(); local t,fprod: FP; for ffprod in ddfact repeat { fprod := ffprod prod; d := ffprod deg; degree fprod = d => ris := cons(fprod,ris); aux := [fprod]; setPoly fprod; while not (empty? aux) repeat { t := ranpol (2@NonNegativeInteger * d); if charF then t := trace2PowMod(t,(n1 * d::Integer - 1$Integer) ::NonNegativeInteger,fprod) else t := exptMod( tracePowMod(t,(d::Integer - 1$Integer) ::NonNegativeInteger,fprod), (p1 quo 2@NonNegativeInteger) ,fprod) - 1$FP; newaux := empty(); for u in aux repeat { g := gcd(u,t); dg := degree g; dg = 0 or dg = degree u => newaux := cons(u,newaux); v := u quo g; if dg = d then ris := cons(inv leadingCoefficient g * g, ris) else newaux := cons(g,newaux); degree v = d => ris := cons(inv leadingCoefficient v * v, ris); newaux := cons(v,newaux); } aux := newaux; } } ris; } ddffact (m:FP):List FP == { import from List fact; ddfact := ddffact1(m,false); empty? ddfact => [m]; separateFactors ddfact; } distdfact(m:FP,test:Boolean):FinalFact == { import from Fraction Z; import from Record(quotient: FP,remainder: FP); import from ParFact; import from fact; factlist:List ParFact := empty(); fln:List FP := empty(); if not ((lcm:F := leadingCoefficient m) = 1) then m := inv lcm * m; if 0 < (d := minimumDegree m) then { m := (monicDivide(m,monomial(1,d))).quotient; factlist := [[monomial(1,1),d::Integer]$ParFact]; } d := degree m; d = 0 => [lcm,factlist]$FinalFact; d = 1 => [lcm,cons([m,d::Integer]$ParFact,factlist)]$FinalFact; test => { fln := ddffact m; factlist := append([[pol,1]$ParFact for pol in fln],factlist); [lcm,factlist]$FinalFact; } factlist := append(notSqFr(m,ddffact),factlist); [lcm,factlist]$FinalFact; } factor (m:FP):Factored FP == { import from FinalFact; import from fact; import from List FP; import from List ParFact; import from fUnion; import from List FFE; m = 0 => 0; flist := distdfact(m,false); makeFR(flist cont::FP, [[[prime],u(irr),u(pow)]$_ Record(flg: Union(nil: 'nil',sqfr: 'sqfr',irred: 'irred',prime: 'prime'),fctr: FP,xpnt: Z) for u in flist factors]); } factorSquareFree (m:FP):Factored FP == { import from FinalFact; import from fact; import from List FP; import from List ParFact; import from fUnion; import from List FFE; m = 0 => 0; flist := distdfact(m,true); makeFR(flist cont::FP, [[[prime],u(irr),u(pow)]$_ Record(flg: Union(nil: 'nil',sqfr: 'sqfr',irred: 'irred',prime: 'prime'),fctr: FP,xpnt: Z) for u in flist factors]); } }