/**
 * Title:        El Gamal Busting System<p>
 * Description:  <p>
 * Copyright:    Copyright (c) Dr. Brooke Stephens, Jeffrey Walton<p>
 * Company:      CMSC 443, UMBC<p>
 * @author Dr. Brooke Stephens, Jeffrey Walton
 * @version 1.0
 */
package stephens;
import java.util.*;
import java.math.BigInteger;


public class DLP {

  // Construct a DLP with parameters alpha, alpha_a (beta), p
  // Use to solve the equation alpha_a = alpha ^ a mod n
  public DLP(long alpha, long alpha_a, long p) {
    this.alpha = BigInteger.valueOf(alpha);
    this.beta = BigInteger.valueOf(alpha_a);
    this.p = BigInteger.valueOf(p);
    this.sqrt_p = sqrt(this.p);
    this.alpha_inv = this.alpha.modInverse(this.p);
    this.r = this.alpha.modPow(this.sqrt_p, this.p);
  }

  // Construct a DLP with parameters alpha, alpha_a (beta), p
  // Use to solve the equation alpha_a = alpha ^ a mod n
  public DLP(BigInteger alpha, BigInteger alpha_a, BigInteger p) {
    this.alpha = alpha;
    this.beta = alpha_a;
    this.p = p;
    this.sqrt_p = sqrt(this.p);
    this.alpha_inv = this.alpha.modInverse(this.p);
    this.r = this.alpha.modPow(this.sqrt_p, this.p);
  }

  public BigInteger SolveDLP() {
    int size = sqrt_p.intValue();
    BinaryHeap one = new BinaryHeap(size+1);  // Table 1
    BinaryHeap two = new BinaryHeap(size+1);  // Table 2

    DLPPair pair;                       // scrap for filling tables

    BigInteger bigA = BigInteger.ONE;   // scrap for building pairs
    BigInteger bigB = beta;             // scrap for building pairs

    // First entry of table 1
    pair = new DLPPair(BigInteger.ZERO, BigInteger.ONE);
    one.insert( pair );

    // First entry of table 2
    pair = new DLPPair(BigInteger.ZERO, bigB);
    two.insert( pair );

    // Here's a funny looking for loop...
    //   We actually only want the following:
    //   for ( i = 1; i <= sqrt_n; i++ )
    BigInteger i = BigInteger.ONE;
    for ( ; i.compareTo(sqrt_p) != 1;
            i= i.add(BigInteger.ONE)     )  {

      bigA = bigA.multiply(r);
      bigA = bigA.mod(p);
      pair = new DLPPair( i, bigA );
      one.insert( pair );

      bigB = bigB.multiply(alpha_inv);
      bigB = bigB.mod(p);
      pair = new DLPPair( i, bigB );
      two.insert( pair );
    }

    DLPPair pairA;      // sort of an iterator
    DLPPair pairB;      // sort of an iterator

    pairA = (DLPPair)one.deleteMin();
    pairB = (DLPPair)two.deleteMin();

    while ( (! one.isEmpty()) && (! two.isEmpty()) ) {
      // Value 1 == Value 2
      //   Found a match
      int res = pairA.GetValue().compareTo( pairB.GetValue() );
      if ( res == 0) {
        BigInteger result = sqrt_p;
        result = result.multiply(pairA.GetExponent());
        result = result.add(pairB.GetExponent());
        return result;
      } else  if ( res == -1) {
        // bump table one
        pairA = (DLPPair)one.deleteMin();
      } else {
        // bump table two
        pairB = (DLPPair)two.deleteMin();
      }
    }
    // No Solution
    return BigInteger.ZERO;

  } // End SolveDLP

  private BigInteger sqrt(BigInteger bi) {
    // Need help here !
    // We can return an approximation, but the
    //   approximation must be equal to or
    //   greater than the actual square root.
    return  BigInteger.valueOf( (long)Math.ceil(Math.sqrt( bi.longValue())) );
  }

  private BigInteger alpha = BigInteger.ZERO;
  private BigInteger alpha_inv = BigInteger.ZERO;
  private BigInteger beta = BigInteger.ZERO;
  private BigInteger p = BigInteger.ZERO;
  private BigInteger sqrt_p = BigInteger.ZERO;
  private BigInteger r = BigInteger.ZERO;  // residue of solving
                                           // alpha ^ sqrt_n mod p

  // Private Class to store pairs for the table.
  //   Of the form (x, y) where x is the exponent,
  //     and y is the value.
  //   compareTo() method is standard, but based on
  //     value (y), not exponet and value.
  private class DLPPair implements Comparable {

    public int hashCode() { return value.toString().hashCode(); }
    public String toString() {
      return exponent.toString() + ", " + value.toString();
    }

    public BigInteger GetExponent() { return exponent; }
    public BigInteger GetValue() { return value; }

    public int compareTo(Object o) {
      DLPPair pair = (DLPPair)o;
       return ( this.GetValue().compareTo(pair.GetValue()) );
    }
    public boolean equals(Object o) {
      DLPPair pair = (DLPPair)o;
      return ( pair.GetExponent().equals(this.GetExponent()) &&
               pair.GetValue().equals(this.GetValue()) );
    }

    public DLPPair(BigInteger exponent, BigInteger value) {
      this.exponent = exponent;
      this.value = value;
    }
    private BigInteger exponent;
    private BigInteger value;

  } // End class Pair

} // End class DLP