open-axiom repository from github
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra ddfact.spad}
\author{Patrizia Gianni, Barry Trager}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package DDFACT DistinctDegreeFactorize}
<<package DDFACT DistinctDegreeFactorize>>=
)abbrev package DDFACT DistinctDegreeFactorize
++ Author: P. Gianni, B.Trager
++ Date Created: 1983
++ Date Last Updated: 22 November 1993
++ Basic Functions: factor, irreducible?
++ Related Constructors: PrimeField, FiniteField
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ 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,FP): C == T
where
F : FiniteFieldCategory
FP : UnivariatePolynomialCategory(F)
fUnion ==> Union("nil", "sqfr", "irred", "prime")
FFE ==> Record(flg:fUnion, fctr:FP, xpnt:Integer)
NNI == NonNegativeInteger
Z == Integer
fact == Record(deg : NNI,prod : FP)
ParFact == Record(irr:FP,pow:Z)
FinalFact == Record(cont:F,factors:List(ParFact))
C == with
factor : FP -> Factored FP
++ factor(p) produces the complete factorization of the polynomial p.
factorSquareFree : FP -> Factored FP
++ factorSquareFree(p) produces the complete factorization of the
++ square free polynomial p.
distdfact : (FP,Boolean) -> FinalFact
++ distdfact(p,sqfrflag) produces the complete factorization
++ of the polynomial p returning an internal data structure.
++ If argument sqfrflag is true, the polynomial is assumed square free.
separateDegrees : FP -> List fact
++ separateDegrees(p) splits the square free polynomial p into
++ factors each of which is a product of irreducibles of the same degree.
separateFactors : List fact -> List FP
++ separateFactors(lfact) takes the list produced by
++ \spadfunFrom{separateDegrees}{DistinctDegreeFactorization}
++ and produces the complete list of factors.
exptMod : (FP,NNI,FP) -> FP
++ exptMod(u,k,v) raises the polynomial u to the kth power
++ modulo the polynomial v.
trace2PowMod : (FP,NNI,FP) -> FP
++ trace2PowMod(u,k,v) produces the sum of \spad{u**(2**i)} for i running
++ from 1 to k all computed modulo the polynomial v.
tracePowMod : (FP,NNI,FP) -> FP
++ tracePowMod(u,k,v) produces the sum of \spad{u**(q**i)}
++ for i running and q= size F
irreducible? : FP -> Boolean
++ irreducible?(p) tests whether the polynomial p is irreducible.
T == add
--declarations
D:=ModMonic(F,FP)
import UnivariatePolynomialSquareFree(F,FP)
--local functions
notSqFr : (FP,FP -> List(FP)) -> List(ParFact)
ddffact : FP -> List(FP)
ddffact1 : (FP,Boolean) -> List fact
ranpol : NNI -> FP
charF : Boolean := characteristic$F = 2
--construct a random polynomial of random degree < d
ranpol(d:NNI):FP ==
k1: NNI := 0
while k1 = 0 repeat k1 := random d
-- characteristic F = 2
charF =>
u:=0$FP
for j in 1..k1 repeat u:=u+monomial(random()$F,j)
u
u := monomial(1,k1)
for j in 0..k1-1 repeat u:=u+monomial(random()$F,j)
u
notSqFr(m:FP,appl: FP->List(FP)):List(ParFact) ==
factlist : List(ParFact) :=empty()
llf : List FFE
fln :List(FP) := empty()
if not one?(lcm:=leadingCoefficient m) then m:=(inv lcm)*m
llf:= factorList(squareFree(m))
for lf in llf repeat
d1:= lf.xpnt
pol := lf.fctr
if not one?(lcp:=leadingCoefficient pol) 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
-- compute u**k mod v (requires call to setPoly of multiple of v)
-- characteristic not equal 2
exptMod(u:FP,k:NNI,v:FP):FP == (reduce(u)$D**k):FP rem v
-- compute u**k mod v (requires call to setPoly of multiple of v)
-- characteristic equal 2
trace2PowMod(u:FP,k:NNI,v:FP):FP ==
uu:=u
for i in 1..k repeat uu:=(u+uu*uu) rem v
uu
-- compute u+u**q+..+u**(q**k) mod v
-- (requires call to setPoly of multiple of v) where q=size< F
tracePowMod(u:FP,k:NNI,v:FP):FP ==
u1 :D :=reduce(u)$D
uu : D := u1
for i in 1..k repeat uu:=(u1+frobenius uu)
(lift uu) rem v
-- compute u**(1+q+..+q**k) rem v where q=#F
-- (requires call to setPoly of multiple of v)
-- frobenius map is used
normPowMod(u:FP,k:NNI,v:FP):FP ==
u1 :D :=reduce(u)$D
uu : D := u1
for i in 1..k repeat uu:=(u1*frobenius uu)
(lift uu) rem v
--find the factorization of m as product of factors each containing
--terms of equal degree .
-- if testirr=true the function returns the first factor found
ddffact1(m:FP,testirr:Boolean):List(fact) ==
p:=size()$F
dg:NNI :=0
ddfact:List(fact):=empty()
--evaluation of x**p mod m
u:= m
du := degree u
setPoly u
mon: FP := monomial(1,1)
v := mon
for k1 in 1.. while k1 <= (du quo 2) repeat
v := lift frobenius reduce(v)$D
g := gcd(v-mon,u)
dg := degree g
dg =0 => "next k1"
if not one? leadingCoefficient g 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)
-- test irreducibility
irreducible?(m:FP):Boolean ==
mf:fact:=first ddffact1(m,true)
degree m = mf.deg
--export ddfact1
separateDegrees(m:FP):List(fact) == ddffact1(m,false)
--find the complete factorization of m, using the result of ddfact1
separateFactors(distf : List fact) :List FP ==
ddfact := distf
n1:Integer
p1:=size()$F
if charF then n1:=length(p1)-1
newaux,aux,ris : List FP
ris := empty()
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*d)
if charF then t:=trace2PowMod(t,(n1*d-1)::NNI,fprod)
else t:=exptMod(tracePowMod(t,(d-1)::NNI,fprod),
(p1 quo 2)::NNI,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)
if degree v=d then ris := cons(inv(leadingCoefficient v)*v,ris)
else newaux := cons(v,newaux)
aux:=newaux
ris
--distinct degree algorithm for monic ,square-free polynomial
ddffact(m:FP):List(FP)==
ddfact:=ddffact1(m,false)
empty? ddfact => [m]
separateFactors ddfact
--factorize a general polynomial with distinct degree algorithm
--if test=true no check is executed on square-free
distdfact(m:FP,test:Boolean):FinalFact ==
factlist: List(ParFact):= empty()
fln : List(FP) :=empty()
--make m monic
if not one?(lcm := leadingCoefficient m) then m := (inv lcm)*m
--is x**d factor of m?
if positive?(d := minimumDegree m) then
m := (monicDivide (m,monomial(1,d))).quotient
factlist := [[monomial(1,1),d]$ParFact]
d:=degree m
--is m constant?
d=0 => [lcm,factlist]$FinalFact
--is m linear?
d=1 => [lcm,cons([m,d]$ParFact,factlist)]$FinalFact
--m is square-free
test =>
fln := ddffact m
factlist := append([[pol,1]$ParFact for pol in fln],factlist)
[lcm,factlist]$FinalFact
--factorize the monic,square-free terms
factlist:= append(notSqFr(m,ddffact),factlist)
[lcm,factlist]$FinalFact
--factorize the polynomial m
factor(m:FP) ==
m = 0 => 0
flist := distdfact(m,false)
makeFR(flist.cont::FP,[["prime",u.irr,u.pow]$FFE
for u in flist.factors])
--factorize the square free polynomial m
factorSquareFree(m:FP) ==
m = 0 => 0
flist := distdfact(m,true)
makeFR(flist.cont::FP,[["prime",u.irr,u.pow]$FFE
for u in flist.factors])
@
\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>>
--The Berlekamp package for the finite factorization is in FINFACT.
<<package DDFACT DistinctDegreeFactorize>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}