// Find the inverse of <number-1> mod <number-2>
// Uses Euclid's algorithm - shows the steps.
// Example: inverse 63741 125
// larger=63741 smaller=553
// 
// 146 = 1*63741 -115*553
// 115 = -3*63741 346*553
// 31 = 4*63741 -461*553
// 22 = -15*63741 1729*553
// 9 = 19*63741 -2190*553
// 4 = -53*63741 6109*553
// 1 = 125*63741 -14408*553
// 0 = -553*63741 63741*553
// 
// Inverse of 63741 mod 553 is 125
// Check: 1
// 
#include <iostream>
#include "bigint.h"
using namespace std;

class Cell {
public:
   Cell *next;
   BigInt *lf, *sf;  // lf = larger factor, sf = smaller factor
   BigInt *number;   // The number this corresponds to
   Cell (BigInt *lf, BigInt *sf, BigInt *number, Cell *next) { 
      this->sf = sf; 
      this->lf = lf; 
      this->number = number;
      this->next = next;
   }
};

BigInt *gcd (BigInt *m, BigInt *n) {
   bool whichone = false;  // false if larger is m, true if smaller is m
   BigInt *r, *d, *larger, *smaller, *factorl, *factors;

   if (n->lessThanBigInt(m)) {
      smaller = n;
      larger = m;
      whichone = false;
   } else {
      larger = n;
      smaller = m;
      whichone = true;
   }

   Cell *head = new Cell(new BigInt(0), new BigInt(1), smaller, NULL);
   BigInt *l = larger->addBigInt(new BigInt(0));
   BigInt *s = smaller->addBigInt(new BigInt(0));

   d = larger->divideBigInt(smaller);
   r = larger->modBigInt(smaller); 
   factors = d->multiplyBigInt(new BigInt(-1));
   factorl = new BigInt(1);
   head = new Cell(factorl,factors,r,head);

   cout << "larger=" << larger << " smaller=" << smaller << "\n\n";

   cout << head->number << " = " << head->lf << "*" << l << " " 
	<< head->sf << "*" << s << "\n";

   while (!r->equalsBigInt(new BigInt("0"))) {
      larger = smaller;
      smaller = r;
      d = larger->divideBigInt(smaller);
      r = larger->modBigInt(smaller);
      factorl = (head->next->lf)->subtractBigInt(d->multiplyBigInt(head->lf));
      factors = (head->next->sf)->subtractBigInt(d->multiplyBigInt(head->sf));
      head = new Cell(factorl,factors,r,head);

      cout << head->number << " = " << head->lf << "*" << l << " " 
	   << head->sf << "*" << s << "\n";
   }
   return (whichone) ? head->next->sf : head->next->lf;
}

int main (int argc, char **argv) {
   if (argc != 3) {
      cout << "Usage: " << argv[0] << " <number> <mod>\n";
      cout << "Find the inverse of <number> modulo <mod>\n";
      exit(0);
   }

   BigInt *number = new BigInt(argv[1]);
   BigInt *mod = new BigInt(argv[2]);
   BigInt *inverse = gcd(number,mod);
   cout << "\nInverse of " << argv[1] << " mod " << argv[2]
	<< " is " << inverse << "\n";
   BigInt *intermed = inverse->multiplyBigInt(new BigInt(argv[1]));
   cout << "Check: " << intermed->modBigInt(new BigInt(argv[2])) << "\n";
}