// Lawrence Bush

// Lab Session:  1
// RCS account:  bushl

//	mmi.h - 	This header file contains a function which 
//			computes the Modular Multiplicative Inverse.


#ifndef MMI_H
#define MMI_H
#include<iostream>


void getxy(const long int & A, const long int & P, long int & X, long int & Y) {
	
	if (P==0) {X=1; Y=0; return;}  // Base Case
		// When P = 0, the equation AX+PY=1 can be solved by
		// X = 1, Y = 0 (or anything)
	
//	R=M%N;
	getxy(P,A%P,X,Y);  // This line recursively call itself
	// until the base case is found. 
	// I reduces by mod and switches A and P.
	// The program never goes past here until the base case
	// is found and regurned.
	
//std::cout<< "prexy   A="<<A<<" P="<<P<<" X="<<X<<" Y="<<Y<<endl;

	// These calculate X and Y from the lower case, and pass
	// them back to the upper case that called this case.
	// Note that the function returns nothing, so the X and Y
	// are passed back by storing them.  They were passed
	// by reference, which allows this.
	long int Xpre=X;
	X=Y;
	Y=Xpre-(A/P)*Y;
//std::cout<< "getxy   A="<<A<<" P="<<P<<" X="<<X<<" Y="<<Y<<endl;
}


int mmi( const long int & A,  const long int & P) {
	if (gcd(A,P) != 1) return -1;//  Otherwise, no MMI exist and return -1
	long int X=0;
	long int Y=0;
	if(A>P) { // we want to start off with A being > than B.
		getxy(A,P,X,Y); // find a Y that satisfies this equation.
		if(Y<0)
	return Y+A; // Since Y is negative, return Y+A which is in the same modulo set.
	else return Y;
	}
	else
		getxy(P,A,Y,X); // We want to start off with A>P, so we switch them.
	//  We must also switch X and Y, so that we solve for X, not Y.
			if(X<0)
	return X+P;
	else return X;

}


#endif