/*----------------------------------------------------------------------+
|      Title:   Mod.java                                                |
|                                                                       |
|      Author:  David E. Joyce                                          |
|           Department of Mathematics and Computer Science              |
|           Clark University                                            |
|           Worcester, MA 01610-1477                                    |
|           U.S.A.                                                      |
|                                                                       |
|           http://aleph0.clarku.edu/~djoyce/                           |
|           djoyce@clarku.edu                                           |
|                                                                       |
|      Date:   Feb, 2006.                                               |
+----------------------------------------------------------------------*/

public class Mod {
  
  // An integer a modulo n.  If the mudulus n = 0, then a is just an integer.  Otherwise,
  // a is represented by a value greater than or equal to 0 and less than n. 
  
  private long value;     // the value, a, is an integer gre 0 and n-1
  private long modulus;   // the modulus. If 0 then the value is just an integer
  
  public Mod(long valueIn, long modulusIn) { 
    modulus = Math.abs(modulusIn);
    if (modulus == 0)
      value = valueIn;
    else {
      value = valueIn % modulus;
      if (value < 0) value += modulus;
    } // if/else
  }  // Mod construtor
  
  public Mod(long modulusIn) {
    value = 0;
    modulus = Math.abs(modulusIn);
  } // Mod constructor
  
  public String toString() {
    return ""+value+" (mod "+modulus+")";
  } // toString
  
  public long getValue() { return value; }
  
  public long getModulus() { return modulus; }
  
  public void setValue(long valueIn) { value = valueIn; }
  
  public boolean equal(Mod b)  
    throws ArithmeticException
  { 
    if (modulus != b.modulus)
      throw new ArithmeticException ("Cannot compare "+this+" and "+b);
    else
      return (value == b.value);
  } // equal
  
  public boolean hasInverse() { return LongPair.GCD(value,modulus)==1; }
  
  // Arithmetic operations.  If the modulus is not the same for all arguments, then
  // an ArithmeticExcetption is thrown.
  // For inverse and division, if the the denominator is not relatively prime to the
  // mudulus, then an ArithmeticException is thrown.
  public Mod plus(Mod b) 
    throws ArithmeticException
  { 
    if (modulus != b.modulus)
      throw new ArithmeticException ("Cannot add "+this+" plus "+b); 
    if (modulus == 0)
      return new Mod(value+b.value,0);
    return new Mod((value+b.value)%modulus,modulus); 
  } // plus
  
  public Mod negation() { return new Mod(modulus-value,modulus); }
 
  public Mod minus(Mod b)  
    throws ArithmeticException
  { 
    if (modulus != b.modulus)
      throw new ArithmeticException ("Cannot subtract "+this+" minus "+b); 
    long c = value-b.value;
    if (c < 0)  c +=modulus;
    return new Mod(c,modulus); 
  } // minus
  
  public Mod from(Mod b)  
    throws ArithmeticException
  { 
    if (modulus != b.modulus)
      throw new ArithmeticException ("Cannot subtract "+this+" from "+b);  
    long c = b.value - value;
    if (c < 0)  c +=modulus;
    return new Mod(c,modulus); 
  } // from
  
  public Mod times(Mod b)  
    throws ArithmeticException
  { 
    if (modulus != b.modulus)
      throw new ArithmeticException ("Cannot multiply "+this+" and "+b); 
    if (modulus == 0) 
      return new Mod(value*b.value,0);
    return new Mod((value*b.value)%modulus,modulus); 
  } // times
  
  public Mod inverse() 
    throws ArithmeticException
  { 
    // convert the congruence  ax = 1 (mod n) to the linear Diophantine equation
    // ax + ny = 1, and solve. 
    if (LongPair.GCD(value,modulus) != 1)
      throw new ArithmeticException ("Cannot invert "+this);
    LongPair solution = LongPair.linearDiophantine(value,modulus,1);
    long c = solution.getFirst() % modulus;
    if (c < 0)  c +=modulus;
    return new Mod(c,modulus);
  } // inverse
  
  public Mod dividedBy(Mod b) { return this.times(b.inverse()); }
  
  public Mod dividedInto(Mod b) { return b.times(this.inverse()); }
  
  public static Mod plus(Mod a, Mod b) { return a.plus(b); }
  
  public static Mod minus(Mod a, Mod b) { return a.minus(b); }
  
  public static Mod times(Mod a, Mod b) { return a.times(b); }
  
  public static Mod dividedBy(Mod a, Mod b) {return a.dividedBy(b); }
  
  // Some functions, reduce and pair, related to the Chinese remainder theorem
  
  // Reduce a (mod n) modulo d.  d must divide n.
  public Mod reduce(long d)
    throws ArithmeticException
  { 
    if (value%d != 0)
      throw new ArithmeticException ("Cannot reduce "+this+" to (mod "+d+")");
    return new Mod(value,d);
  } // reduce
  
  // Use the Chinese remainder theorem to pair  a (mod n)  with  b (mod m)
  // to get  x (mod mn).  The two moduli must be relatively prime.
  public Mod pair(Mod b) 
    throws ArithmeticException
  { 
    if (LongPair.GCD(modulus,b.modulus) != 1)
      throw new ArithmeticException ("Cannot pair "+this+" with "+b);
    // Solve the linear Diophantine equation   a + ny = b + mz,
    // that is, the equation  ny - mx = (b - a)
    LongPair solution = LongPair.linearDiophantine(modulus,-b.modulus,b.value-value);
    // Then  x = a + ny
    return new Mod(value+modulus*solution.getFirst(),modulus*b.modulus);
  } // pair
  
  public static Mod pair(Mod a, Mod b) { return a.pair(b); }
  
  // Compute a raised to the bth power modulo n.  If b is negative
  // it is assumed that a is relatively prime to n.
  public Mod power(long b)
    throws ArithmeticException
  {
    if (b == 0) return new Mod(0,modulus);
    if (b == 1) return new Mod(value,modulus);
    if (b < 0) {
      if (LongPair.GCD(value,modulus) != 1)
        throw new ArithmeticException 
          ("Cannot compute "+this+" raised to the power "+b);
      return inverse().power(-b);
    } // if (b<0)    
    Mod s = this.power(b/2);
    s = s.times(s);
    if (b%2==0) return s;
    else return this.times(s);
  } // power
  
  // Determine if n is a 2-pseudoprime relative to b by checking of
  // b raised to the (n-1)st power is congruent to 1 modulo n
  public static boolean pseudoprime(long n, long b) {
    Mod x = new Mod(b,n);
    return (x.power(n-1).value == 1);
  } // pseudoprime


} // Mod