(* SAC Integer Polynomial System Definition Module. *)

DEFINITION MODULE SACIPOL;


FROM MASSTOR IMPORT LIST;


PROCEDURE IPABS(RL,A: LIST): LIST;
(*Integral polynomial absolute value.  A is an integral polynomial in
r variables.  B is the absolute value of A.*)


PROCEDURE IPCRA(M,ML,MLP,RL,A,AL: LIST): LIST;
(*Integral polynomial chinese remainder algorithm.  M is a positive
integer.  m is a positive beta-integer.  gcd(M,m)=1.  mp is the
inverse of H sub m of M.  A is an integral polynomial in r variables
whose coefficients belong to Z prime sub M, r non-negative.  a is a
polynomial in r variables over Z sub m.  AS is the unique integral
polynomial in r variables with coefficients in Z prime sub MS, where
MS=M*m, which is congruent to A modulo M and to a modulo m.*)


PROCEDURE IPDER(RL,A,IL: LIST): LIST;
(*Integral polynomial derivative.  A is an integral polynomial in r
variables.  1 le i le r.  B is the derivative of A with respect to
its i-th variable.*)


PROCEDURE IPDIF(RL,A,B: LIST): LIST;
(*Integral polynomial difference.  A and B are integral polynomials in
r variables, r ge 0.  C=A-B.*)


PROCEDURE IPDMV(RL,A: LIST): LIST;
(*Integral polynomial derivative, main variable.  A is an integral
polynomial in r variables.  B is the derivative of A with respect to
its main variable.*)


PROCEDURE IPEMV(RL,A,AL: LIST): LIST;
(*Integral polynomial evaluation of main variable.  A is an integral
polynomial in r variables.  a is an integer.
B(x(1), ...,x(r-1))=A(x(1), ...,x(r-1),a).*)


PROCEDURE IPEVAL(RL,A,IL,AL: LIST): LIST;
(*Integral polynomial evaluation.  A is an integral polynomial
in r variables.  1 le i le r.  a is an integer.  B(x(1), ...,
x(i-1),x(i+1), ...,x(r))=A(x(1), ...,x(i-1),a,x(i+1), ...,x(r)).*)


PROCEDURE IPEXP(RL,A,NL: LIST): LIST;
(*Integral polynomial exponentiation.  A is an integral polynomial in
r variables, r ge 0.  n is a non-negative integer.  B=A**n.*)


PROCEDURE IPFCB(V: LIST): LIST;
(*Integral polynomial factor coefficient bound.  V is the degree vector
of a non-zero integral polynomial A.  b is a non-negative integer such
that if b(1)* ...*b(k) divides A then the product of the infinity norms
of the b(i) is less than or equal to 2**b times the infinity norm of A.
Gelfonds bound is used.*)


PROCEDURE IPFRP(RL,A: LIST): LIST;
(*Integral polynomial from rational polynomial.  A is a rational
polynomial in r variables, r ge 0, each of whose base coefficients is
an integer.  B is a converted to integral polynomial representation.*)


PROCEDURE IPGSUB(RL,A,SL,L: LIST): LIST;
(*Integral polynomial general substitution.  A is an integral
polynomial in r variables, r ge 1.  L is a list (b(1), ...,b(r)) of
integral polynomials in s variables, s ge 1.  C(y(1), ...,y(s))=
A(b(1)(y(1), ...,y(s)), ...,b(r)(y(1), ...,y(s))).*)


PROCEDURE IPHDMV(RL,A,KL: LIST): LIST;
(*Integral polynomial higher derivative, main variable.  A is an
integral polynomial in r variables.  k is a non-negative
gamma-integer B is the k-th derivative of A with respect to its main
variable.*)


PROCEDURE IPIHOM(RL,D,A: LIST): LIST;
(*Integral polynomial mod ideal homomorphism.  D is a list (d sub 1, ...,
d sub r-1) of non-negative beta-integers, r ge 0.  A is an r-variate 
integral polynomial.  B=A mod (x sub 1 ** d sub 1, ...,x sub
r-1 ** d sub r-1).*)


PROCEDURE IPIP(RL,AL,B: LIST): LIST;
(*Integral polynomial integer product.  a is an integer.  B is an
integral polynomial in r variables.  C=a*B.*)


PROCEDURE IPIPR(RL,D,A,B: LIST): LIST;
(*Integral polynomial mod ideal product.  D is a list (d sub 1, ...,
d sub r-1) of non-negative beta-integers, r ge 1.  A and B belong to
Z(x sub 1, ...,x sub r-1,y)/(x sub 1 **d sub 1, ...,x sub r-1 ** d
sub r-1).  C=A*B.*)


PROCEDURE IPIQ(RL,A,BL: LIST): LIST;
(*Integral polynomial integer quotient.  A is an integral polynomial
in r variables.  b is a non-zero integer which divides A.  C=A/b.*)


PROCEDURE IPMAXN(RL,A: LIST): LIST;
(*Integral polynomial maximum norm.  A is an integral polynomial
in r variables.  b is the maximum norm of A.*)


PROCEDURE IPNEG(RL,A: LIST): LIST;
(*Integral polynomial negative.  A is an integral polynomial in r
variables, r ge 0.  B=-A.*)


PROCEDURE IPONE(RL,A: LIST): LIST;
(*Integral polynomial one.  A is an integral polynomial in r
variables.  If A=1 then t=1, otherwise t=0.*)


PROCEDURE IPPROD(RL,A,B: LIST): LIST;
(*Integral polynomial product.  A and B are integral polynomials in r
variables, r ge 0.  C=A*B.*)


PROCEDURE IPPSR(RL,A,B: LIST): LIST;
(*Integral polynomial pseudo-remainder.  A and B are integral
polynomials in r variables, B non-zero.  C is the pseudo-remainder
of A and B.*)


PROCEDURE IPQ(RL,A,B: LIST): LIST;
(*Integral polynomial quotient.  A and B are integral polynomials in
r variables, r ge 0.  B is a non-zero divisor of A.  C=A/B.*)


PROCEDURE IPQR(RL,A,B: LIST; VAR Q,R: LIST);
(*Integral polynomial quotient and remainder.  A and B are integral
polynomials in r variables with B non-zero.  Q and R are the unique
integral polynomials such that either B divides A, Q=A/B and R=0 or
else B does not divide A and A=BQ+R with deg(R) minimal.*)


PROCEDURE IPRAN(RL,KL,QL,N: LIST): LIST;
(*Integral polynomial, random.  k is a positive beta-digit.  q is a
rational number q1/q2 with 0 lt q1 le q2 lt beta.  N is a list
(n sub r, ...,n sub 1) of non-negative beta-digits, r ge 0.  A is a
random integral polynonial in r variables with deg sub i of a le n
sub i for 1 le i le r.  Max norm of A lt 2**k and q is the
probability that any particular term of a has a non-zero coefficient.*)


PROCEDURE IPREAD( VAR RL,A,V: LIST);
(*Integral polynomial read.  The integral polynomial A is read from the
input stream.  r, non-negative, is the number of variables of A and V
is the variable list of A.  Any number of preceding blanks are skipped.*)


PROCEDURE IPSIGN(RL,A: LIST): LIST;
(*Integral polynomial sign.  A is an integral polynomial in r
variables.  s is the sign of A.*)


PROCEDURE IPSMV(RL,A,B: LIST): LIST;
(*Integral polynomial substitution for main variable.  A is an
integral polynomial in r variables, x(1), ...,x(r).  B is an
integral polynomial in x(1), ...,x(r-1).  C(x(1), ...,x(r-1))=
A(x(1), ...,x(r-1),B(x(1), ...,x(r-1))).*)


PROCEDURE IPSUB(RL,A,IL,B: LIST): LIST;
(*Integral polynomial substitution.  A is an integral polynomial in
r variables, x(1), ...,x(r).  1 le i le r.  B is an integral
polynomial in x(1), ...,x(i-1).  C(x(1), ...,x(i-1),x(i+1), ...,
x(r))=A(x(1), ...,x(i-1),B(x(1), ...,x(i-1)),x(i+1), ..., x(r)).*)


PROCEDURE IPSUM(RL,A,B: LIST): LIST;
(*Integral polynomial sum.  A and B are integral polynomials in r
variables, r ge 0.  C=A+B.*)


PROCEDURE IPSUMN(RL,A: LIST): LIST;
(*Integral polynomial sum norm.  A is an integral polynomial in r
variables, r non-negative.  b is the sum norm of A.*)


PROCEDURE IPTPR(RL,D,A,B: LIST): LIST;
(*Integral polynomial truncated product.  D is a list (d sub 1, ...,d sub r)
of non-negative beta-integers, r ge 1.  A and B belong to
Z(x sub 1, ...,x sub r)/(x sub 1 **d sub 1, ...,x sub r ** d sub r).
C=A*B.*)


PROCEDURE IPTRAN(RL,A,T: LIST): LIST;
(*Integral polynomial translation.  A is an integral polynomial in r
variables, r ge 1.  T is a list (tr, ...,t1) of integers.
B(x1, ...,xr)=A(x1+t1, ...,xr+tr).*)


PROCEDURE IPTRMV(RL,A,HL: LIST): LIST;
(*Integral polynomial translation, main variable.  A is an integral
polynomial in r variables, r ge 1.  h is an integer.
B(x1, ...,xr)=A(x1, ...,x(r-1),xr+h).*)


PROCEDURE IPTRUN(RL,D,A: LIST): LIST;
(*Integral polynomial truncation.  D is a list (d sub 1, ...,d sub r)
of non-negative beta-integers, r ge 0.  A is an r-variate integral
polynomial.  B=A mod (x sub 1 ** d sub 1, ..., x sub r ** d sub r).*)


PROCEDURE IPWRIT(RL,A,V: LIST);
(*Integral polynomial write.  A is an integral polynomial in r
variables, r ge 0.  V is a variable list for A.  A is written
in the output stream in external canonical form.*)


PROCEDURE IUPBEI(A,CL,ML: LIST): LIST;
(*Integral univariate polynomial binary rational evaluation, integer
output.  A is a univariate integral polynomial.  c is an integer.  m
is a non-negative beta-integer.  b=2**(n*m)*A(c/2**m) where n=deg(A).
b is an integer.*)


PROCEDURE IUPBES(A,AL: LIST): LIST;
(*Integral univariate polynomial binary rational evaluation of sign.
A is a univariate polynomial.  a is a binary rational number.  
s=sign(A(a)).*)


PROCEDURE IUPBHT(A,KL: LIST): LIST;
(*Integral univariate polynomial binary homothetic transformation.  A
is a non-zero univariate integral polynomial.  k is a gamma-integer.
B(x)=2**(-h)*A(2**k*x) where h is uniquely determined so that B is
an integral polynomial not divisible by 2.*)


PROCEDURE IUPBRE(A,AL: LIST): LIST;
(*Integral univariate polynomial binary rational evaluation.  A is a
univariate integral polynomial.  a is a binary rational number.  
B=A(a), a binary rational number.*)


PROCEDURE IUPCHT(A: LIST): LIST;
(*Integral univariate polynomial circle to half-plane transformation.
A is a non-zero univariate integral polynomial.  Let n=deg(A).  Then
B(x)=(x+1)**n*A(1/(x+1)), a univariate integral polynomial.*)


PROCEDURE IUPNT(A: LIST): LIST;
(*Integral univariate polynomial negative transformation.  A is a 
univariate integral polynomial.  B(x)=A(-x).*)


PROCEDURE IUPTPR(NL,A,B: LIST): LIST;
(*Integral univariate polynomial truncated product.  n is a non-
negative integer.  A and B are integral univariate polynomials.  
C(x)=A(x)*B(x) (modulo x**n) and C=0 or deg(C) lt n.*)


PROCEDURE IUPTR(A,HL: LIST): LIST;
(*Integral univariate polynomial translation.  A is a univariate
integral polynomial.  h is an integer.  B(x)=A(x+h).*)


PROCEDURE IUPTR1(A: LIST): LIST;
(*Integral univariate polynomial translation by 1.  A is a univariate
integral polynomial.  B(x)=A(x+1).*)


END SACIPOL.