Extended Euclidean algorithm
Extension of Euclidean algorithm computing gcd and Bézout coefficients.
The extended Euclidean algorithm builds on the standard Euclidean algorithm. Besides finding the greatest common divisor (gcd) of two integers *a* and *b*, it also calculates the integers *x* and *y* from Bézout's identity, which satisfy *ax* + *by* = gcd(*a*, *b*). This version is often written as xgcd(*a*, *b*). It is a certifying algorithm, since the gcd is the only value that both divides the inputs and fits that equation. With almost no extra work, it can also provide the quotients of *a* and *b* divided by their gcd. A very similar algorithm exists for polynomials, computing the polynomial gcd and Bézout coefficients for two univariate polynomials.
The extended Euclidean algorithm is especially useful when *a* and *b* are coprime. In that case, *x* becomes the modular multiplicative inverse of *a* modulo *b*, and *y* becomes the modular multiplicative inverse of *b* modulo *a*. Likewise, the polynomial version can compute multiplicative inverses in algebraic field extensions, including finite fields of non-prime order. Because of this, both extended Euclidean algorithms are widely used in cryptography. For instance, finding the modular multiplicative inverse is a crucial step in generating key pairs for the RSA public-key encryption method.
In the standard Euclidean algorithm, only the remainders from each division step are kept; the quotients are discarded. The extended algorithm, however, makes use of those successive quotients. Given inputs *a* and *b*, the standard algorithm generates a sequence of quotients *q₁*, …, *qₖ* and remainders *r₀*, …, *rₖ₊₁*, where *r₀* = *a*, *r₁* = *b*, and each later remainder is defined by *rᵢ₊₁* = *rᵢ₋₁* − *qᵢrᵢ*, with 0 ≤ *rᵢ₊₁* < |*rᵢ*|. The inequalities in this Euclidean division uniquely determine *qᵢ* and *rᵢ₊₁* from *rᵢ₋₁* and *rᵢ*. The process stops when a remainder *rₖ₊₁* is reached.
- field
- Arithmetic and computer programming
- known_for
- Computing the greatest common divisor and Bézout coefficients; modular multiplicative inverse; used in cryptography, particularly RSA key-pair derivation
Lore & Background
The extended Euclidean algorithm builds upon the standard Euclidean algorithm by not discarding the quotients from each division step. In the standard method, only the sequence of remainders is tracked, beginning with the two input numbers and continuing until a zero remainder is reached; the greatest common divisor is the last non-zero remainder. For the extended algorithm, these successive quotients are used to compute two additional sequences. The process stops at the same point as the standard algorithm, and the final non-zero remainder remains the greatest common divisor. The two extra sequences then provide the coefficients of Bézout's identity, which are integers that satisfy a linear combination equaling the greatest common divisor. This makes the algorithm certifying, as the computed greatest common divisor is the only number that can both satisfy this equation and divide the original inputs. The algorithm also yields, with almost no extra cost, the quotients of the original numbers divided by their greatest common divisor. A notable property arises when both inputs are positive and the first is larger: the Bézout coefficients produced are the minimal pair, uniquely satisfying specific inequalities. This property ensures that if the inputs fit within an unsigned integer data type, the coefficients can be computed in the corresponding signed type without integer overflow. The algorithm is particularly useful when the inputs are coprime, as the coefficients then become modular multiplicative inverses of one number modulo the other. A closely related version exists for univariate polynomials over a field, computing the polynomial greatest common divisor and Bézout coefficients. This polynomial variant enables the computation of multiplicative inverses in algebraic field extensions and finite fields of non-prime order, making both algorithms widely applied in cryptography, notably in the derivation of RSA key-pairs.
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.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record