Extended Euclidean & Modular Inverse

To find d such that e * d ≡ 1 (mod φ(n)) (the RSA private exponent), we need the modular inverse.

Extended Euclidean Algorithm finds gcd(a, b) AND coefficients x, y such that a*x + b*y = gcd(a, b):

If gcd(a, m) = 1, then a*x + m*y = 1, which means a*x ≡ 1 (mod m). So x mod m is the modular inverse.

The recursion above is the clearest way to see the identity, but crypto libraries write this as a loop instead. Two reasons, and neither is style: a loop has no recursion depth for an adversarial input to exhaust, and its shape is fixed from the outside, which is where any constant-time implementation has to start. The coefficients come out identical either way.

Example: inverse of 3 mod 11:

3 * 4 = 12 ≡ 1 (mod 11). So 3^-1 ≡ 4 (mod 11).

This is exactly how RSA computes the private key d:

d = modinv(e, φ(n))

Where φ is Euler's totient and e is the public exponent.