Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor.

Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout's identity of two univariate polynomials.

The extended Euclidean algorithm is particularly useful when a and b are coprime. With that provision, 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 one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method.

$r_{k}$ is the greatest common divisor of the input $a=r_{0}$ and $b=r_{1}.$

The Bézout coefficients are $s_{k}$ and $t_{k},$ that is $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$

The quotients of a and b by their greatest common divisor are given by $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ and $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$

Euclidean domain

Linear congruence theorem

Kuṭṭaka

. The Art of Computer Programming. Addison-Wesley. Volume 2, Chapter 4.

Knuth, Donald

Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

Extended Euclidean algorithm

Euclidean domain

Linear congruence theorem

Kuṭṭaka

Knuth, Donald

Thomas H. Cormen

Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)