(* SAC Modular Univariate Polynomial Factorization Definition Module. *)

DEFINITION MODULE SACMUFAC;


FROM MASSTOR IMPORT LIST;


PROCEDURE MCPMV(NL,L: LIST): LIST; 
(*Matrix of coefficients of polynomials, with respect to main variable.
L is a list (L(1), ...,L(k)) of k, ge 1, non-zero polynomials with
degrees less than n.  n is a positive beta-integer.  M is the matrix
with m(1,il)+m(2,i)*x+ ...+m(n,i)*x**(n-1)=L(i) for 1 le i le
k.*)


PROCEDURE MIUPSE(M,A,B,S,T,C: LIST;  VAR U,V: LIST); 
(*Modular integral univariate polynomial, solution of equation.  M is a
positive integer.  A,B,S,T and C belong to Z sub M (x) with ldcf(A) a
unit, deg(T) lt deg(A) and A*S+B*T=1.  U and V are the unique elements
of Z sub M (x) such that A*U+B*V=C, with deg(V) lt deg(A).*)


PROCEDURE MUPBQP(PL,A: LIST): LIST; 
(*Modular univariate polynomial berlekamp q polynomials construction.
p is a prime beta-integer.  A is a univariate polynomial over Z sub p
with deg(A) ge 2.  Q is the list (Q(0), ...,Q(n-1)), where Q(i)(x)=
rem(x**(p*i),A(x)) and n=deg(A).*)


PROCEDURE MUPDDF(PL,A: LIST): LIST; 
(*Modular univariate polynomial distinct degree factorization.  p is
a prime beta-integer.  A is a monic squarefree univariate polynomial
over Z sub p, with deg(A) ge 2.  L is a list ((n(1),A(1)), ...
,(n(k),A(k))) where each n(i) is a positive integer, n(1) lt
n(2) lt ...lt n(k), and A(i) is the product of all irreducible monic
factors of A  of degree n(i).*)


PROCEDURE MUPFBL(PL,A: LIST): LIST; 
(*Modular univariate polynomial factorization-berlekamp algorithm.
p is a prime beta-integer.  A is a monic squarefree univariate poly-
nomial, with deg(A) ge 2.  L is a list of all the monic irreducible
factors of A of positive degree.*)


PROCEDURE MUPFS(PL,A,B,DL: LIST): LIST; 
(*Modular univariate polynomial factorization, special.  p is a prime
beta-integer. A is a monic squarefree polynomial in Z sub p(x),deg(A)
ge 2.  B is a list (B(1), ...,B(r)) of monic univariate polynomials
over Z sub p, which constitute a basis for the space of all polynomials
C of degree less than deg(A) such that A is a divisor of C**p-C.
Further-more, B(1)=1.  d is a positive beta-integer such that A has
no irreducible factor of degree less than d.  L is a list
consisting of all the monic irreducible factors of A of positive
degree.*)


END SACMUFAC.