Back to doug's directory

File information
Filename: egcd.c Uploaded: Wed, 3rd Mar 2010 20:47:14
Size (bytes): 2.75 KiB md5 checksum: a9d4cb444ee8deb1be5bd45e7c02ccac
Uploader doug Download: egcd.c
Description:

Nice little implementation of the extended Euclidean Algorithm I needed it for some crypto work I was doing (ElGamel).

gcd(m, n) to work out the greatest common divisor. egcd(m, n) prints it's workings as it goes and returns the gcd.

/*
	Nice little implementation of the extended Euclidean Algorithm
	I needed it for some crypto work I was doing (ElGamel).
 
	Author: doug@nulldigital.net;
	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[1];
}
 
int main(int argc, char ** argv) {
	if (argc > 2) {
		int x, y;
		x = atoi(argv[1]);
		y = atoi(argv[2]);
		printf("extended gcd = %d\n", egcd(x, y));
		printf("simple gcd = %d\n", gcd(x, y));
	} else {
		printf("Usage: %s integer1 integer2\n", argv[0]);
	}
}
 
Powered by Debian, Guinness, and excessive quantities of caffeine and sugar.