-- $Id: zp.cecil,v 1.1 1997/04/30 22:40:04 grove Exp $
-- CSE 521 Miniproject: Fast Fourier Transform
-- Molly Brown & Brian Dewey
-- 30 April 1997

-- This is the integers mod p class.
-- Note:  the modulus must be a prime in order to get the 
-- required field properties.

------------------------------------------------------------
-- Further note:  zp can't find an Nth_root_of_unity.  For that,
-- we use the specific subclass big_zp w/ a definite modulus
-- and predictible algorithm for generating Nth roots of unity.
------------------------------------------------------------

template object zp isa alg_field;
  field number(@:zp): integer := 0; -- Default to 0.
  field modulus(@:zp): integer := 1; -- Default to 1.

  ------------------------------------------------------------
  -- Utility routines

  -- Note:  I don't check that num is positive.  That might be a good
  -- thing for the future.  In the meantime, give it a number that's
  -- legit for this modulus.
  method new_zp(num@:integer, mod@:integer):zp {
      if (mod >= 0,
	  {concrete object isa zp {
	      number := num,
	      modulus := mod
	  }},
	  {error("Modulus must be positive")})
  }

  method print_string(i@:zp) {
      -- First, normalize what we've got.
      let var temp := i.number;
      while({ temp < 0 },
	    { temp := temp + i.modulus });
      temp := temp %_ov i.modulus;
      temp.print_string || " (mod " || i.modulus.print_string || ")"
  }

  ------------------------------------------------------------
  -- The required ring methods.

  -- First, addition.
  method +(i1@:zp, i2@:zp): zp {
      -- We need to add numbers of the same modulus.
      if(not(i1.modulus = i2.modulus),
	 { error("Adding modular numbers with different bases.") });
      concrete object isa zp {
	  number := (i1.number +_ov i2.number),
	  modulus := i1.modulus
      };
  }

  -- Multiplication
  method *(i1@:zp, i2@:zp): zp {
      -- We need to multiply numbers of the same modulus.
      if(not(i1.modulus = i2.modulus),
	 { error("Multiplying modular numbers with different bases.") });
      concrete object isa zp {
	  number := (i1.number *_ov i2.number) %_ov i1.modulus,
	  modulus := i1.modulus
      }
  }

  -- Unary minus
  method -(i@:zp): zp {
      concrete object isa zp {
	  number  := i.modulus -_ov i.number,
	  modulus := i.modulus
      };
  }

  -- The zero "operator"
  method zero(i@:zp): zp {
      concrete object isa zp {
	  number := 0,
	  modulus := i.modulus
      };
  }

  -- And the one "operator"
  method one(i@:zp): zp {
      concrete object isa zp {
	  number := 1,
	  modulus := i.modulus
      };
  }

  ------------------------------------------------------------
  -- Multiplicative inverse; req'd to be a field.
  method multInverse(i@:zp): zp {
      let t := extended_euclid(i.number, i.modulus);
      -- Now, we need to normalize t.second w/ respect to
      -- the modulus.
      let var mult_inverse := t.second;
      while({ mult_inverse < 0 },
	    { mult_inverse := mult_inverse +_ov i.modulus });
      if(t.first = 1,
	 { new_zp(mult_inverse, i.modulus) },
	 { error("Modulus was not a prime.")})
  }

  method extended_euclid(a:integer, b:integer):triple[integer,integer,integer] {
      -- This comes straight from Cormen, Leiserson, & Rivest
      if(b = 0,
	 { new_triple(a, 1, 0) },
	 { let t_prime := extended_euclid(b, a %_ov b);
	   new_triple(t_prime.first, 
		      t_prime.third,
		      t_prime.second -_ov (a/b) *_ov t_prime.third) }
	 )
  }

  method from_integer(i@:zp, N:integer):zp {
      new_zp(N %_ov i.modulus, i.modulus)
  }

  -- It's an error to try to find the Nth root of a field w/ an
  -- arbitrary modulus.  Subclass zp to get the desired properties.
  method Nth_root_of_unity(i@:zp, N:integer):zp {
      error("I can't find an Nth root of unity in an arbitrary modulus.")
  }