(* ----------------------------------------------------------------------------
 * $Id: MASFF.mi,v 1.2 1992/10/15 16:29:41 kredel Exp $
 * ----------------------------------------------------------------------------
 * This file is part of MAS.
 * ----------------------------------------------------------------------------
 * Copyright (c) 1989 - 1992 Universitaet Passau
 * ----------------------------------------------------------------------------
 * $Log: MASFF.mi,v $
 * Revision 1.2  1992/10/15  16:29:41  kredel
 * Changed rcsid variable
 *
 * Revision 1.1  1992/09/28  17:38:31  kredel
 * Initial revision
 *
 * ----------------------------------------------------------------------------
 *)

IMPLEMENTATION MODULE MASFF;

(* MAS Finite Field Implementation Module. *)


(* import lists and declarations. *)

FROM MASSTOR IMPORT LIST, SIL, BETA,
                    LIST1, SFIRST, SRED, LENGTH, INV, 
                    FIRST, RED, COMP, ADV;

FROM SACLIST IMPORT LIST3, CONC, CINV, ADV2, COMP2, FIRST2, 
                    EQUAL, RED2, SECOND, LIST2;

FROM SACM IMPORT MIHOM, MIINV;
FROM SACRN IMPORT RNRED;
FROM SACPOL IMPORT PLDCF, PDEG, PBIN, PINV;

FROM SACIPOL IMPORT IPONE;

FROM SACMPOL IMPORT MIPDIF, MIPSUM, MIPHOM, MIUPQR, MIPPR, MIPNEG, MIPRAN; 

FROM DIPC IMPORT PFDIP, DIPFP; 

FROM DIPI IMPORT DIIPWR, DIIPRD; 

(* 
FROM SACPGCD IMPORT IPPGSD, IPSRP;
*)

CONST rcsidi = "$Id: MASFF.mi,v 1.2 1992/10/15 16:29:41 kredel Exp $";
CONST copyrighti = "Copyright (c) 1989 - 1992 Universitaet Passau";


PROCEDURE FFCOMP(R,S: LIST): LIST;
(*Finite field comparison.  R and S are finite field elements.
t=0 if R=S, t=1 else. *)
VAR   t: LIST;
BEGIN
(*1*) t:=EQUAL(R,S); 
      IF t = 1 THEN t:=0 ELSE t:=1 END;  
      RETURN(t);
(*4*) END FFCOMP;


PROCEDURE FFDIF(p,M,AL,BL: LIST): LIST; 
(*Finite field difference.  AL and BL are elements of F(p)(alpha) for 
some prime integer p and some algebraic number alpha.  M is the 
minimal polynomial for alpha. CL=AL-BL.*)
VAR   CL: LIST; 
BEGIN
(*1*) CL:=MIPDIF(1,p,AL,BL); 
      RETURN(CL); 
(*4*) END FFDIF; 


PROCEDURE FFEXP(p,M,A,NL: LIST): LIST; 
(*Finite field exponentiation.  A is an element of F(p)(alpha) for 
some prime integer p and some algebraic number alpha.  M is the 
minimal polynomial for alpha.  nl is a non-negative beta-integer.  
B=A**nl.*)
VAR   B, KL: LIST; 
BEGIN
(*1*) (*nl less than or equal to 1.*) 
      IF NL = 0 THEN B:=FFFINT(p,M,1); RETURN(B); END; 
      IF NL = 1 THEN B:=A; RETURN(B); END; 
(*2*) (*recursion.*) KL:=NL DIV 2; B:=FFEXP(p,M,A,KL); 
      B:=FFPROD(p,M,B,B); 
      IF NL > 2*KL THEN B:=FFPROD(p,M,B,A); END; 
(*5*) RETURN(B); END FFEXP; 
 

PROCEDURE FFFINT(p,M,A: LIST): LIST; 
(*Finite field element from integer.  A is an integer. B is A 
converted to an element of F(p)(alpha), for some prime integer p and 
some algebraic number alpha. M is the minimal polynomial for alpha. *)
VAR   B, C, BL: LIST; 
BEGIN
(*1*) (*convert. *) BL:=MIHOM(p,A); B:=PINV(0,BL,1);  
(*5*) RETURN(B); END FFFINT; 


PROCEDURE FFHOM(p,M,A: LIST): LIST; 
(*Finite field homomorpism.  A is an univariate integral polynomial, 
B is A converted to an element of F(p)(alpha), for some prime integer p 
and some algebraic number alpha. M is the minimal polynomial for 
alpha. *)
VAR   B, C, D: LIST; 
BEGIN
(*1*) (*get remainder.*) B:=MIPHOM(1,p,A); 
      MIUPQR(p,B,M, C, D); 
(*5*) RETURN(D); END FFHOM; 


PROCEDURE FFINV(p,M,AL: LIST): LIST; 
(*Finite field inverse.  AL is a nonzero element of F(p)(alpha) 
for some prime integer p and some algebraic number alpha.  M is the
minimal polynomial for alpha.  BL=1/AL.*)
VAR   AL1, AL2, AL3, BL, CL, DL, EL, QL, RL, VL1, VL2, VL3: LIST; 
BEGIN
(*1*) AL1:=M; AL2:=AL; VL1:=0; RL:=1; VL2:=LIST2(0,RL); 
      LOOP DL:=PLDCF(AL2); CL:=MIINV(p,DL); CL:=LIST2(0,CL);
           VL2:=MIPPR(1,p,CL,VL2); 
           IF PDEG(AL2) = 0 THEN BL:=VL2; RETURN(BL); END; 
           AL2:=MIPPR(1,p,CL,AL2); MIUPQR(p,AL1,AL2, QL,AL3); 
           EL:=MIPPR(1,p,QL,VL2); VL3:=MIPDIF(1,p,VL1,EL); AL1:=AL2; 
           AL2:=AL3; VL1:=VL2; VL2:=VL3; 
           END; 
(*4*) RETURN(BL); END FFINV; 


PROCEDURE FFNEG(p,M,AL: LIST): LIST; 
(*Finite field negation.  AL is an element of F(p)(alpha) for some 
prime integer p and some algebraic number alpha. M is the minimal 
polynomial for alpha. BL= -AL.*)
VAR   BL: LIST; 
BEGIN
(*1*) BL:=MIPNEG(1,p,AL); 
      RETURN(BL); 
(*4*) END FFNEG; 


PROCEDURE FFONE(R: LIST): LIST; 
(*Finite field one.  R is a finite field element.  s=1 if R=1,
s=0 else. *)
VAR   t: LIST;
BEGIN
(*1*) t:=IPONE(1,R); RETURN(t);
(*4*) END FFONE;


PROCEDURE FFPROD(p,M,AL,BL: LIST): LIST; 
(*Finite field product.  AL and BL are elements of F(p)(alpha) for 
some prime integer p and some algebraic number alpha.  M is the 
minimal polynomial of alpha.  CL=AL+BL.*)
VAR   CL, CLP, QL: LIST; 
BEGIN
(*1*) CLP:=MIPPR(1,p,AL,BL); MIUPQR(p,CLP,M, QL,CL); 
(*4*) RETURN(CL); END FFPROD; 


PROCEDURE FFQ(p,M,AL,BL: LIST): LIST; 
(*Finite field quotient.  AL and BL, BL nonzero, are elements of 
F(p)(alpha) for some prime integer p and some algebraic number 
alpha. M is the minimal polynomial for alpha.  CL=AL/BL.*)
VAR   CL, DL: LIST; 
BEGIN
(*1*) IF AL = 0 THEN CL:=0; ELSE DL:=FFINV(p,M,BL); 
         CL:=FFPROD(p,M,AL,DL); END; 
      RETURN(CL); 
(*4*) END FFQ; 


PROCEDURE FFRAND(p,M,NL: LIST): LIST;
(*Finite field element, random.  n is a positive beta-integer le deg(M). 
A random finite field element R of F(p)(alpha) for some prime integer p 
and some algebraic number alpha.  M is the minimal polynomial for 
alpha. R is generated using MIPRAN(1,p,n/deg(M),(deg(M))). *) 
VAR   R, d, D, n, q: LIST;  
BEGIN
(*1*) d:=PDEG(M)-1; D:=LIST1(d); IF d <= 0 THEN d:=1 END; 
      n:=NL; IF n <= 0 THEN n:=1 END; IF n > d THEN n:=d END; 
      q:=RNRED(n,d); 
      R:=MIPRAN(1,p,q,D); RETURN(R); 
(*9*) END FFRAND; 


PROCEDURE FFREAD(V: LIST): LIST;
(*Finite field read.  The finite field element R is read from the input
stream.  V is the varaible list. Any preceding blanks are skipped. *)
VAR   CL, RL: LIST;
BEGIN
(*1*) CL:=DIIPRD(V); PFDIP(CL, RL,CL); 
      RETURN(CL); 
(*9*) END FFREAD; 


PROCEDURE FFSUM(p,M,AL,BL: LIST): LIST; 
(*Finite field sum.  AL and BL are elements of F(p)(alpha) for some 
prime integer p and some algebraic number alpha.  M is the minimal 
polynomial for alpha.  CL=AL+BL.*)
VAR   CL: LIST; 
BEGIN
(*1*) CL:=MIPSUM(1,p,AL,BL); RETURN(CL); 
(*4*) END FFSUM; 


PROCEDURE FFWRITE(R, V: LIST);
(*Finite field write. R is a finite field element. V is the varaible 
list. R is written to the output stream. *)
VAR   CL: LIST;
BEGIN
(*1*) CL:=DIPFP(1,R); DIIPWR(CL,V); 
(*9*) END FFWRITE; 


END MASFF.
(* -EOF- *)