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.
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.
More precisely, the standard Euclidean algorithm with a and b as input, consists of computing a sequence
of remainders such that It is the main property of Euclidean division that the inequalities on the right define uniquely
The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows The computation also stops when
The following table shows how the extended Euclidean algorithm proceeds with input 240 and 46.
Finally the last two entries 23 and −120 of the last row are, up to the sign, the quotients of the input 46 and 240 by the greatest common divisor 2.
alternate in sign and strictly increase in magnitude, which follows inductively from the definitions and the fact that
Otherwise, everything which precedes in this article remains the same, simply by replacing integers by polynomials.
A second difference lies in the bound on the size of the Bézout coefficients provided by the extended Euclidean algorithm, which is more accurate in the polynomial case, leading to the following theorem.
The second way to normalize the greatest common divisor in the case of polynomials with integer coefficients is to divide every output by the content of
If the input polynomials are coprime, this normalisation also provides a greatest common divisor equal to 1.
If one divides everything by the resultant one gets the classical Bézout's identity, with an explicit common denominator for the rational numbers that appear in it.
To implement the algorithm that is described above, one should first remark that only the two last values of the indexed variables are needed at each step.
In a programming language which does not have this feature, the parallel assignments need to be simulated with an auxiliary variable.
This leads to the following code: The quotients of a and b by their greatest common divisor, which is output, may have an incorrect sign.
at the end: However, in many cases this is not really an optimization: whereas the former algorithm is not susceptible to overflow when used with machine integers (that is, integers with a fixed upper bound of digits), the multiplication of old_s * a in computation of bezout_t can overflow, limiting this optimization to inputs which can be represented in less than half the maximal size.
This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by The proof of this algorithm relies on the fact that s and t are two coprime integers such that as + bt = 0, and thus
To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.
A notable instance of the latter case are the finite fields of non-prime order.
If n is a positive integer, the ring Z/nZ may be identified with the set {0, 1, ..., n-1} of the remainders of Euclidean division by n, the addition and the multiplication consisting in taking the remainder by n of the result of the addition and the multiplication of integers.
Bézout's identity asserts that a and n are coprime if and only if there exist integers s and t such that Reducing this identity modulo n gives Thus t, or, more exactly, the remainder of the division of t by n, is the multiplicative inverse of a modulo n. To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of n is not needed, and thus does not need to be computed.
Also, for getting a result which is positive and lower than n, one may use the fact that the integer t provided by the algorithm satisfies |t| < n. That is, if t < 0, one must add n to it at the end.
The extended Euclidean algorithm is also the main tool for computing multiplicative inverses in simple algebraic field extensions.
An important case, widely used in cryptography and coding theory, is that of finite fields of non-prime order.
In fact, if p is a prime number, and q = pd, the field of order q is a simple algebraic extension of the prime field of p elements, generated by a root of an irreducible polynomial of degree d. A simple algebraic extension L of a field K, generated by the root of an irreducible polynomial p of degree d may be identified to the quotient ring
Thus, to complete the arithmetic in L, it remains only to define how to compute multiplicative inverses.
For example, if the polynomial used to define the finite field GF(28) is p = x8 + x4 + x3 + x + 1, and a = x6 + x4 + x + 1 is the element whose inverse is desired, then performing the algorithm results in the computation described in the following table.
Since 1 is the only nonzero element of GF(2), the adjustment in the last line of the pseudocode is not needed.
Thus, the inverse is x7 + x6 + x3 + x, as can be confirmed by multiplying the two elements together, and taking the remainder by p of the result.