Extended Euclid and modular inverses
Watch the remainders shrink while each row keeps r = x·a + y·n. When the remainder hits 1, x is the inverse. Toy RSA gives d.
Each row keeps the invariant rᵢ = xᵢ·a + yᵢ·n. When the remainder hits 0, the row above holds gcd(a, n), and if it equals 1, xᵢ mod n is a⁻¹. The defaults are textbook toy RSA: p = 61, q = 53, φ(n) = 3120, e = 17. The inverse is the private exponent d.
| i | qᵢ | rᵢ | xᵢ | yᵢ |
|---|---|---|---|---|
| 0 | 3120 | 0 | 1 | |
| 1 | 17 | 1 | 0 | |
| 2 | 183 | 9 | -183 | 1 |
| 3 | 1 | 8 | 184 | -1 |
| 4 | 1 | 1 | -367 | 2 |
| 5 | 8 | 0 | 3120 | -17 |
gcd(17, 3120) = 1, so a⁻¹ ≡ 2753 (mod 3120). Check: 17 · 2753 mod 3120 = 1.
What to notice
- Every row satisfies rᵢ = xᵢ·a + yᵢ·n. That invariant is the whole proof of Bézout's identity.
- The number of rows grows like log n, which is why inverses are cheap even for 2048-bit numbers.
- Try a = 6, n = 3120: the gcd is 6, so there is no inverse. That is why RSA needs gcd(e, φ(n)) = 1.