/*
 * Extended Euclidean Algorithm - calculate the inverse 'a' modulo 'n'
 *
 * by Sam Giuliano (modified version of code from
 *                         "Applied Cryptography" by Schneier p.246-248)
 *
 *
 *  to compile: g++ -o inverse e.C
 *
 *  NOTE: I have successfully compiled this on GL, but have not been
 *        able to get it to compile properly on Research.
 *
 */
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <Integer.h>

Integer & ExtBinEuclid(Integer &u, Integer &v, 
		       Integer &u1, Integer &u2, 
		       Integer &u3)
{
  Integer k, t1, t2, t3, tmp;

  if (u < v) {
    tmp = u;
    u = v;
    v = tmp;
  }
  for (k=0; (((u & 0x01) == 0) && ((v & 0x01) == 0)); ++k) {
    u >>= 1; v >>= 1;
  }
  u1 = 1; u2 = 0; u3 = u; t1 = v; t2 = u-1; t3 = v;
  do {
    do {
      if ((u3 & 0x01) == 0) {
        if ((u1 & 0x01) == 1) {
          u1 += v; u2 += u;
	} else if ((u2 & 0x01) == 1) {
          u1 += v; u2 += u;
        }
        u1 >>= 1; u2 >>= 1; u3 >>=1;
      }
      if (((t3 & 0x01) == 0) || u3 < t3) {
	tmp = u1;
	u1 = t1;
	t1 = tmp;

	tmp = u2;
	u2 = t2;
	t2 = tmp;

	tmp = u3;
	u3 = t3;
	t3 = tmp;
      }
    }while ((u3 & 0x01) == 0);
    while (u1 < t1 || u2 < t2) {
      u1 += v; 
      u2 += u;
    }
    u1 -= t1; u2 -= t2; u3 -= t3;
  }while (t3 > 0);
  while (u1 >= v && u2 >= u) {
    u1 -= v; u2 -= u;
  }
  u1 <<= k; u2 <<= k; u3 <<= k;
  return (u1);
}

main (int argc, char **argv) {
  Integer a, b, gcd, u, v;

  cout << "Enter e: ";
  cin >> u;

  cout << "Enter (p-1)*(q-1): ";
  cin >> v;

  if (u <= 0 || v <= 0) {
    cerr << "Arguments must be positive!" << endl;
    return -2;
  }
  ExtBinEuclid(u, v, a, b, gcd);
  cout << a << " * " << u << " + (-"
       << b << ") * " << v << " = " << gcd << endl;
  if (gcd == 1)
    cout << "the inverse of " << v << " mod " << u << " is: "
         << u - b << endl;
  return 0;
}