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

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));