// greatest common divisor algorithm

#include "types.h"

#ifndef _GCD
#define _GCD

/*	if a is returned as a positive number, then b (d) was a negative before 
	conversion for use in encryption algorithms (d = mod - abs(b) if b is negative  */
	
long long gcd(long long m, long long n, uelong *a=0, uelong *b=0);





// b is the inverse modulo
long long gcd(elong x, elong y, uelong *a, uelong *b){

	elong rem;
	elong a1=1, a2=0, b1=0, b2=1, t=0, q=0;
	elong largest=0, smallest=0;

	if (y>x){
		int temp =y;
		y=x;
		x=temp;
	}
	
	largest = x, smallest=y; /* keep x, y as largest, smallest for 
					later use if b is negative */
	
	while((rem=largest%smallest)!=0){
		q = largest/smallest;
		largest=smallest;
		smallest=rem;
		t=a2;
		a2 = a1 - (q*a2);
		a1 = t;
		t = b2;
		b2 = b1 - (q*b2);
		b1 = t;
	}
	
	if (a!=0 && b!=0){
		if (a2 <0) 
			a2=y+a2;
		*a = a2;
		
		if (b2 <0) 
			b2=x+b2;
		*b = b2; 
	}	
	
return smallest;	
}


#endif