So far, so good. Now, how do you go about finding the inverse of a modulo n? There are a couple of ways. Euclid’s algorithm can also compute the inverse of a number modulo n. Sometimes this is called the extended Euclidean algorithm.

Here’s the algorithm in C++:

    #define isEven(x)   ((x & 0x01) == 0)
    #define isOdd(x)    (x & 0x01)
    #define swap(x,y)   (x ^= y, y ^= x, x ^= y)

    void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3)
    {
        // warning: u and v will be swapped if u < v
        int k, t1, t2, t3;

        if (*u < *v) swap(*u,*v);
        for (k = 0; isEven(*u) && isEven(*v); ++k) {
    	*u >>= 1; *v >>= 1;
        }
        *u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u-1; t3 = *v;
        do {
    	do {
    	    if (isEven(*u3)) {
    		if (isOdd(*u1) || isOdd(*u2)) {
    		    *u1 += *v; *u2 += *u;
    		}
    		*u1 >>= 1; *u2 >>= 1; *u3 >>= 1;
    	    }
    	    if (isEven(t3) || *u3 < t3) {
    		swap(*u1,t1); swap(*u2,t2); swap(*u3,t3);
    	    }
    	} while (isEven(*u3));
    	while (*u1 < t1 || *u2 < t2) {
    	    *u1 += *v; *u2 += *u;
    	}
    	*u1 -= t1; *u2 -= t2; *u3 -= t3;
        } while (t3 > 0);
        while (*u1 >= *v && *u2 >= *u) {
    	*u1 -= *v; *u2 -= *u;
        }
        *u1 <<= k; *u2 <<= k; *u3 <<= k;
    }

    main(int argc, char **argv) {
        int a, b, gcd;

        if (argc < 3) {
    	cerr << "Usage: xeuclid u v" << endl;
    	return -1;
        }
        int u = atoi(argv[1]);
        int v = atoi(argv[2]);
        if (u <= 0 || v <= 0) {
    	cerr << "Arguments must be positive!" << endl;
    	return -2;
        }
        // warning: u and v will be swapped if u < v
        ExtBinEuclid(&u, &v, &a, &b, &gcd);
        cout << a << " * " << u << " + (-"
    	<< b << ") * " << v << " = " << gcd << endl;
        if (gcd == 1)
    	cout << "the inverse of " << v << " mod " << u << " is: "
    	    << u - b << endl;
        return 0;
    }

I’m not going to prove that it works or give the theory behind it. Details can be found in [863], or in any of the number theory texts previously listed.

The algorithm is iterative and can be slow for large numbers. Knuth showed that the average number of divisions performed by the algorithm is:

.843*log₂(n) + 1.47

Solving for Coefficients

Euclid’s algorithm can be used to solve this class of problems: Given an array of m variables x₁, x₂,...x_m, find an array of m coefficients, u₁, u₂...u_m, such that

u₁*x₁ + ...+ u_m*x_m = 1

Fermat’s Little Theorem

If m is a prime, and a is not a multiple of m, then Fermat’s little theorem says

am ^-1 ≡ 1 (mod m)

(Pierre de Fermat, pronounced “Fair-ma, ” was a French mathematician who lived from 1601 to 1665. This theorem has nothing to do with his last theorem.)

The Euler Totient Function

There is another method for calculating the inverse modulo n, but it’s not always possible to use it. The reduced set of residues mod n is the subset of the complete set of residues that is relatively prime to n. For example, the reduced set of residues mod 12 is {1, 5, 7, 11}. If n is prime, then the reduced set of residues mod n is the set of all numbers from 1 to n- 1. The number 0 is never part of the reduced set of residues for any n not equal to 1.

The Euler totient function, also called the Euler phi function and written as φ(n), is the number of elements in the reduced set of residues modulo n. In other words, φ(n) is the number of positive integers less than n that are relatively prime to n (for any n greater than 1). (Leonhard Euler, pronounced “Oiler, ” was a Swiss mathematician who lived from 1707 to 1783.)

If n is prime, then φ(n) = n- 1. If n = pq, where p and q are prime, then φ(n) = (p- 1)(q- 1). These numbers appear in some public-key algorithms; this is why.

According to Euler’s generalization of Fermat’s little theorem, if gcd(a,n) = 1, then

a^φ(n) mod n = 1

Now it is easy to compute a^-1 mod n:

x = a^φ(n)-1 mod n

For example, what is the inverse of 5, modulo 7? Since 7 is prime, φ(7) = 7- 1 = 6. So, the inverse of 5, modulo 7, is

5^6-1 mod 7 = 5⁵ mod 7 = 3

Both methods for calculating inverses can be extended to solve for x in the general problem (if gcd(a,n) = 1):

(a*x) mod n = b

Using Euler’s generalization, solve

x = (b*a ^φ(n)-1) mod n

Using Euclid’s algorithm, solve

x = (b*(a^-1 mod n)) mod n

In general, Euclid’s algorithm is faster than Euler’s generalization for calculating inverses, especially for numbers in the 500-bit range. If gcd(a,n) ≠ 1, all is not lost. In this general case, (a*x) mod n = b, can have multiple solutions or no solution.

Chinese Remainder Theorem

If you know the prime factorization of n, then you can use something called the Chinese remainder theorem to solve a whole system of equations. The basic version of this theorem was discovered by the first-century Chinese mathematician, Sun Tse.