Compute the inverse of n module m.

modular_inversion.c

#include "stdio.h"

// Compute the solution x to x*n % m == 1 using the Generalized Euclidean Agorithm
int inverse(int n, int m){
	int t0 = 0, t1 = 1;
	int s0 = 1, s1 = 0;
	int r = m - 1; // Just to get started
	int a = m;
	int b = n;
	int q, s, t;
	while(r > 0) {
		q = a/b;
		r = a - b*q;
		s = s0 - q*s1;
		t = t0 - q*t1;
		a = b;
		b = r;
		t0 = t1;
		t1 = t;
		s0 = s1;
		s1 = s;
	}
	// If we find a negative value, we calculate it modulo m
	return t0 < 0 ? t0 + m : t0;
}

// Compute the solution x to x*n % m == 1 searching each possiblity
int naive_inverse(int n, int m){
	int d = 0;
	for(d = 2; d < m || d*n % m == 1; d++);
	return d;
}

int main(){
	// Tests
	int e = 5;
	int phi = 23;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	e = 11;
	phi = 60;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	e = 3;
	phi = 120;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	e = 23;
	phi = 120;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	e = 47;
	phi = 352;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	e = 153;
	phi = 352;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	// Edge cases (we'll not use them)
	e = 1;
	phi = 2;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	// Edge cases (we'll not use them, but it still works)
	e = 2;
	phi = 2;
	printf("==| e = %3d phi = %3d |==\n", e, phi);
	printf("Naive inverse:  %3d\n", inverse(e, phi));
	printf("Euclid inverse: %3d\n\n", inverse(e, phi));

	return 0;
}