Extended Euclidean Algorithm & Modular Inverse

Why cryptography needs it

Many ciphers do arithmetic modulo m and need to undo a multiplication: “what x makes b·x ≡ 1 (mod m)?” That x is the modular inverse of b. You need it for:

• the RSA private key, d = e⁻¹ mod φ(n),
• decrypting the Hill and affine ciphers,
• adding points on elliptic curves,
• the Chinese remainder theorem.

The extended Euclidean algorithm computes it quickly, even for 2048-bit numbers.

Euclid’s algorithm

The key fact: gcd(a, b) = gcd(b, a mod b). Anything that divides a and b also divides the remainder, and the other way round. So keep dividing until the remainder is 0:

161 = 5 × 28 + 21
 28 = 1 × 21 + 7
 21 = 3 × 7  + 0      →  gcd = 7, the last non-zero remainder

As a picture: draw a 161 × 28 rectangle. Cut off as many 28 × 28 squares as fit (5), which leaves a 21 × 28 strip. Cut 21 × 21 squares from that strip (1), leaving 21 × 7. Then three 7 × 7 squares fill it exactly. The gcd is the largest square that tiles the whole rectangle. The model draws exactly this.

The extended version

Along the way, keep track of how each remainder is built from a and b. Every remainder can be written as a·s + b·t, and the table updates s and t with the same quotient q as the remainders:

q = r1 div r2
r = r1 − q·r2      s = s1 − q·s2      t = t1 − q·t2
then shift:  r1 ← r2, r2 ← r   (same for s and t)
start:       r1 = a, r2 = b,  s1 = 1, s2 = 0,  t1 = 0, t2 = 1

When r2 reaches 0: gcd = r1 and a·s1 + b·t1 = gcd. That equation is Bézout’s identity.

Example: a = 161, b = 28

q	r1	r2	r	s1	s2	s	t1	t2	t
5	161	28	21	1	0	1	0	1	−5
1	28	21	7	0	1	−1	1	−5	6
3	21	7	0	1	−1	4	−5	6	−23
	7	0		−1			6

So gcd = 7, and indeed 161·(−1) + 28·6 = −161 + 168 = 7 ✓.

Modular inverse

To find b⁻¹ mod m, run the table with a = m. If gcd(m, b) = 1, then m·s + b·t = 1. Taking both sides mod m removes the m·s term, leaving b·t ≡ 1 (mod m), so the inverse is t mod m.

Example: 7⁻¹ mod 26

q	r1	r2	r	t1	t2	t
3	26	7	5	0	1	−3
1	7	5	2	1	−3	4
2	5	2	1	−3	4	−11
2	2	1	0	4	−11	26
	1	0		−11

gcd = 1 and t = −11, so 7⁻¹ ≡ −11 + 26 = 15. Check: 7 × 15 = 105 = 4·26 + 1 ✓. You only need the t columns for an inverse.

For RSA with φ(n) = 3120 and e = 17, the same table ends with t = −367, so d = −367 + 3120 = 2753.

Code

def ext_euclid(a, b):
    """Return (g, s, t) with a*s + b*t = g = gcd(a, b)."""
    r1, r2, s1, s2, t1, t2 = a, b, 1, 0, 0, 1
    while r2 > 0:
        q = r1 // r2
        r1, r2 = r2, r1 - q * r2
        s1, s2 = s2, s1 - q * s2
        t1, t2 = t2, t1 - q * t2
    return r1, s1, t1

def mod_inverse(b, m):
    g, s, t = ext_euclid(m, b)
    if g != 1:
        return None                 # no inverse: b and m share a factor
    return t % m

print(ext_euclid(161, 28))          # (7, -1, 6)
print(ext_euclid(240, 46))          # (2, -9, 47)
print(mod_inverse(7, 26))           # 15
print(mod_inverse(17, 3120))        # 2753
print(mod_inverse(4, 26))           # None

Since Python 3.8, pow(b, -1, m) returns the modular inverse directly.

#include <iostream>
using namespace std;

// Returns gcd(a, b) and sets s, t so that a*s + b*t = gcd.
long long extEuclid(long long a, long long b, long long &s, long long &t) {
    long long r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
    while (r2 > 0) {
        long long q = r1 / r2;
        long long r = r1 - q * r2, sNew = s1 - q * s2, tNew = t1 - q * t2;
        r1 = r2; r2 = r;
        s1 = s2; s2 = sNew;
        t1 = t2; t2 = tNew;
    }
    s = s1; t = t1;
    return r1;
}

// Inverse of b modulo m, or -1 if it does not exist.
long long modInverse(long long b, long long m) {
    long long s, t;
    if (extEuclid(m, b, s, t) != 1) return -1;
    return ((t % m) + m) % m;
}

int main() {
    long long s, t;
    long long g = extEuclid(161, 28, s, t);
    cout << g << " " << s << " " << t << "\n";   // 7 -1 6
    cout << modInverse(7, 26) << "\n";           // 15
    cout << modInverse(17, 3120) << "\n";        // 2753
}

Common mistakes

• Leaving the inverse negative. If t comes out negative, add m. Both t and t + m are correct mod m, but the answer is normally given between 0 and m − 1.
• Not checking the gcd. If the gcd isn’t 1, there is no inverse, and the t you computed means nothing.
• Putting the numbers in the wrong order. For b⁻¹ mod m, start with r1 = m and r2 = b, and read the answer from the t column.
• Stopping one row too early. The gcd is the last non-zero remainder: read r1 when r2 has become 0.