#egcd.c

/*
	Nice little implementation of the extended Euclidean Algorithm
	I needed it for some crypto work I was doing (ElGamel).
	
	Author: doug@neverfear.org;
	Date: 2007-03-30
	Compile: gcc -o egcd egcd.c
	Usage: egcd integer1 integer2
*/
#include <stdio.h>

 // simple convert something like -33 (mod 17) to 1 (mod 17)
int posmod(int neg, int mod) {
	while(neg < 0) {
		neg += mod;
	}
	return neg % mod;
}

/*
	This is a simple implementation of code which will work
	though and get the greatest common divisor. It's probably
	not the cutest, but it is one which works and was easy for
	me to think though with my head :-P
*/
int gcd(int m, int n) {
int x = 0;
	if (!(m > n)) {
		m = m ^ n;
		n = m ^ n;
		m = m ^ n;
	}
	// m is above n
	while(n != 0) {
		x = n % m;
		n = m - x;
		m = m - n;
		// swap
		m = m ^ n;
		n = m ^ n;
		m = m ^ n;
	}
	return m;
}


// calc the gcd and display the workings
int egcd(int m, int n) {
int quotient = 0;
int a[2], b[2]; // 0 - now, 1 - last
int x[3], y[3]; // 0 - now, 1 - last
int remainder = 0;
	
	printf("%dX + %dY = d\n", m, n);
	printf("+--------+---------+---------+---------+---------+---------+\n");
	printf("|       A|        B|        Q|        R|        X|        Y|\n");
	printf("+--------+---------+---------+---------+---------+---------+\n");
	a[0] = m;
	b[0] = n;
	
	
	x[1] = 0;
	y[1] = 1;
	x[2] = 1;
	y[2] = 0;
	
	
	do {
		
		quotient = a[0] / b[0];
		remainder = a[0] - (quotient * b[0]);
		
		a[1] = a[0];
		b[1] = b[0];
		
		printf("|% 8d| % 8d| % 8d| % 8d| % 8d| % 8d|\n", a[0], b[0], quotient, remainder, x[1], y[1]);
		
		a[0] = b[1];
		b[0] = a[1] - (b[1] * quotient);
		
		y[0] = y[2] - (y[1] * quotient);
		
		x[0] = x[2] - (x[1] * quotient);
		x[2] = x[1];
		y[2] = y[1];
		x[1] = x[0];
		y[1] = y[0];
		
	} while(remainder > 0);
	printf("+--------+---------+---------+---------+---------+---------+\n\n");
	printf("d = egcd(%d, %d) = %d\n", m, n, b[1]);
	printf("X = %d, Y = %d\n", x[2], y[2]);
	printf("%dx(%d) + %dx(%d) = %d\n\n", m, x[2], n, y[2], b[1]);
	printf("Summary\n");
	printf("d = %d is the greatest common divisor\n", b[1]);
	printf("X = %d is the Multiplicative inverse of %d mod %d\n", x[2], m, n);
	printf("=> %d %% %d = %d\n", m, n, m % n);
	printf("=> %d x %d = %d (mod %d)\n\n",m % n, x[2], posmod((m % n) * x[2], n), n);
	printf("Y = %d is the Multiplicative inverse of %d mod %d\n", y[2], n, m);
	printf("=> %d %% %d = %d\n", n, m, n % m);
	printf("=> %d x %d = %d (mod %d)\n\n", n % m, y[2], posmod((n % m) * y[2], m), m);
	return b[0];
}

int main(int argc, char ** argv) {
	if (argc > 2) {
		int x, y;
		x = atoi(argv[1]);
		y = atoi(argv[2]);
		egcd(x, y);
		printf("simple gcd = %d\n", gcd(x, y));
	} else {
		printf("Usage: %s integer1 integer2\n", argv[0]);
	}
}