Extended Euclidean algorithm

Lore & Background

The standard Euclidean algorithm proceeds by a succession of Euclidean divisions whose quotients are not used; only the remainders are kept. For the extended algorithm, the successive quotients are used. The standard algorithm with a and b as input computes a sequence of quotients q₁, …, qₖ and a sequence of remainders r₀, …, rₖ₊₁ such that r₀ = a, r₁ = b, and rᵢ₊₁ = rᵢ₋₁ − qᵢ rᵢ with 0 ≤ rᵢ₊₁ < |rᵢ|. The computation stops when a remainder rₖ₊₁ is zero; the greatest common divisor is then the last nonzero remainder rₖ.

Reader's Guide

The extended Euclidean algorithm proceeds similarly but adds two other sequences, s and t, starting with s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1. At each step, the same quotients qᵢ are used to update sᵢ₊₁ and tᵢ₊₁. This yields the Bézout coefficients. The algorithm is particularly useful when a and b are coprime, as then x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows computation of the multiplicative inverse in algebraic field extensions and, in particular, in finite fields of non-prime order. Both extended Euclidean algorithms are widely used in cryptography; the computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method.

Did You Know?

• The extended Euclidean algorithm computes integers x and y such that ax + by = gcd(a, b).
• It is a certifying algorithm because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.
• When a and b are coprime, x is the modular multiplicative inverse of a modulo b.
• The algorithm is widely used in cryptography, particularly in RSA key-pair derivation.