Extended Euclidean algorithm and Modular multiplicative inverse

The computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses.

Extended Euclidean algorithm

The algorithm works as follows. Assume that m is larger than n and start by dividing m by n to yield a quotient \( q_1 \) and a nonnegative remainder \( r_1 \) that is less than n. Then we have

\( m = q_1n + r_1. \hspace{32mm} (1) \)

Now since \( r_1 \lt n \) we may divide n by \( r_1 \) to obtain a second quotient and remainder:

\( n = q_2r_1 + r_2. \hspace{32mm} (2) \)

Continue in this way, dividing \( r_1 \) by \( r_2 \), \( r_2 \) by \( r_3 \), and so on. The remainders get smaller each time but cannot go below zero. So the process must stop at some point with a remainder of 0: that is, with a division that comes out exactly.

For instance, if m = 165 and n = 70, the algorithm generates the sequence of divisions

\( 165 = 2 × 70 + 25, \hspace{32mm} (3) \)
\( 70 = 2 × 25 + 20, \hspace{32mm} (4) \)
\( 25 = 1 × 20 + 5, \hspace{32mm} (5) \)
\( 20 = 4 × 5 + 0. \hspace{32mm} (6) \)

The process guarantees that the last nonzero remainder, 5 in this case, is the highest common factor of m and n. On the one hand, the last line shows that 5 is a factor of the previous remainder 20. Now the last-butone line shows that 5 is also a factor of the remainder 25 that occurred one step earlier, because 25 is expressed as a combination of 20 and 5. Working back up the algorithm we conclude that 5 is a factor of both m = 165 and n = 70. So 5 is certainly a common factor of m and n.

On the other hand, the last-but-one line shows that 5 can be written as a combination of 25 and 20 with integer coefficients. Since the previous line shows that 20 can be written as a combination of 70 and 25 we can write 5 in terms of 70 and 25:

\( 5 = 25 − 20 = 25 − (70 − 2 × 25) = 3 × 25 − 70. \)

Continuing back up the algorithm we can express 25 in terms of 165 and 70 and conclude that

\( 5 = 3 × (165 − 2 × 70) − 70 = 3 × 165 − 7 × 70. \)

This shows that 5 is the highest common factor of 165 and 70 because any factor of 165 and 70 would automatically be a factor of \( 3 × 165 − 7 × 70 \): that is, a factor of 5. Along the way we have shown that the highest common factor can be expressed as a combination of the two original numbers m and n.

(The Princeton Companion to Mathematics - Part III Mathematical Concepts - III.22 The Euclidean Algorithm and Continued Fractions, by Keith Ball)

Bézout’s identity — Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

The integers x and y are called Bézout coefficients for (a, b); they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm.

\( m’m + n’n = gcd(m, n) \)

\(
\begin{align*}
\begin{cases} \text{if }m = 0, \text{we simply take } m’=0 \text{ and } n’=1 \text{ as } gcd(0, n)=n \\
\text{Otherwise }m \neq 0, \text{we let }r=n \bmod m=n-\lfloor \frac{n}{m} \rfloor m
\end{cases}
\end{align*}
\)

\( \overline{r}r + \overline{m}m = gcd(r,m) \)

\( \text{ as } gcd(m, n) = gcd(r, m) \)
\( \overline{r}(n-\lfloor \frac{n}{m} \rfloor m) + \overline{m}m = m’m + n’n \implies \)
\( (\overline{m}-\lfloor \frac{n}{m} \rfloor \overline{r})m + \overline{r}n = m’m + n’n \implies \)

\(
\begin{align*}
\begin{cases} m’ = \overline{m}-\lfloor \frac{n}{m} \rfloor \overline{r} \\
n’ = \overline{r}
\end{cases}
\end{align*}
\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class ExtendedEuclid {
    public static void main(String[] args) {
        int m = 12, n = 18;
        EEResult re = extendedEuclid(m, n);
        System.out.printf("%d*%d + %d*%d = %d", re.a, m, re.b, n, re.d);
    }

    public static EEResult extendedEuclid(int m, int n) {
        EEResult re = new EEResult();
        if (m==0) {
            re.d = n;
            re.a = 0;
            re.b = 1;
            return re;
        }
        re = extendedEuclid(n%m, m);
        int d = re.d;
        int a = re.b - (n/m)*re.a;
        int b = re.a;
        re.d = d;
        re.a = a;
        re.b = b;
        return re;
    }

    static class EEResult {
        int d;
        int a;
        int b;
    }
}

Modular multiplicative inverse

Finding modular multiplicative inverses also has practical applications in the field of cryptography, i.e. public-key cryptography and the RSA Algorithm.

\( \displaystyle ax\equiv b{\pmod {m}} \)

\( \displaystyle x\equiv a^{-1}{\pmod {m}} \)

\(
\begin{align*}
\begin{cases} d_1 \equiv 35^{-1}{\pmod {3}} = 2 \\
d_2 \equiv 21^{-1}{\pmod {5}} = 1 \\
d_3 \equiv 15^{-1}{\pmod {7}} = 1
\end{cases}
\end{align*}
\)

1
2
3
4
5
import java.math.BigInteger;

BigInteger.valueOf(35).modInverse(BigInteger.valueOf(3));
BigInteger.valueOf(21).modInverse(BigInteger.valueOf(5));
BigInteger.valueOf(15).modInverse(BigInteger.valueOf(7));