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


//	modexp.h - 	This header file contains a modexp function 
//			which recursively calls itself to 
//			calculate and return X^N mod P.


#ifndef MODEXP_H
#define MODEXP_H
// The modexp function's integers must be unsigned long, so it can handle the
// possibility of larger intermediate values.
// This is not necessary in the other functions and program parts, since
// the integers are less than or equal to N.  It is also not possible 
// in the mmi function, because it needs to use negative numbers.
int modexp(unsigned long int x, unsigned long int n, unsigned long int p) {
	if (n==0) return 1; // base case (x^0 % p = 1)
	if (n==1) return x%p; // other base cass (x^1 % p = x % p)
	if ( (n % 2) == 0 )  // if even 
	// square the x and halve the exponent, 
	// also mod each intermediate value.
		return modexp(((x%p)*(x%p))%p,(n/2),p)%p;
	else  // if odd
 // square the x and halve the exponent all * X, 
 // also mod each intermediate value.
		return (modexp( ((x%p)*(x%p))%p,(n/2),p )*(x%p))%p;
}



#endif