Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

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
_{2}(*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 _{1}*,

*u*= 1_{1}*x_{1}+ ...+ u_{m}*x_{m}

*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^{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.

Previous | Table of Contents | Next |