Extended Euclidean algorithm

Contents
Examples
Example
See also
References
External links

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 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.

r0,…,rk+1 of remainders such that

ri+1 from rk+1 which is zero; the greatest common divisor is then the last nonzero remainder rk+1=0 and gives

b=r1.
The Bézout coefficients are gcd⁡(a,b)=rk=ask+btk
The quotients of a and b by their greatest common divisor are given by ∓ is opposite to |si|≤⌊b2gcd⁡(a,b)⌋and|ti|≤⌊a2gcd⁡(a,b)⌋

for x.

Together with the general form of all Bézout coefficient pairs, these inequalities imply that the extended Euclidean algorithm provides the unique pair that simultaneously minimizes the absolute values of both coefficients, called the minimal Bézout pair.

It also means that if a and b fit into an unsigned integer data type, a computer program can compute the Bézout coefficients in the corresponding signed integer type without integer overflow.

Examples

edit

The following table shows how the extended Euclidean algorithm proceeds with input 2 in the column "remainder". The computation stops at row 6, because the remainder in it is 23 and 240 by the greatest common divisor Remainder ri''i'' "}},"i":0}}]}'>si ti 04646 = 5 × 1 − 1 0 − 10 = 4 × 0 − −4 1 − 6 = 1 × 1 − 5 −5 − 4 = 1 × −4 − −9 21 − 4 ÷ 4 − 0 −9 = −120

The following example uses a more compact notation. The greatest common divisor of g=gcd(68,30)↑−−(−2)=gcd(8,30)(−3)−−↑ −2 times a=1a+0b and 0≤ri+1<|ri|, the sequence rk+1=0. This proves that the algorithm stops, eventually.

From the equation gcd⁡(a,b)=gcd⁡(r0,r1)=gcd⁡(rk,rk+1)=gcd⁡(rk,0)=rk. Until this point, the proof is the same as that of the classical Euclidean algorithm.

The recurrence relations, for i=0 they reduce to

i+1 follow from the computation

sk+1 and sk, it implies that

sk+1 divides b=dsk+1. Dividing by a=−dtk+1. Hence, a and b are both positive and a<b, it can be seen that the (a,b) under the Extended Euclidean Algorithm are, up to initial t and (a,b) case reduces to the s2 is 1 and si alternate in sign and strictly increase in magnitude, which follows inductively from the definitions and the fact that i=1 holds because b"}}'>a>b. The same is true for the gcd⁡(a,b)≠min⁡(a,b)). Thus, noticing that sk,tk are larger than or equal to in absolute value than any previous as+bt=gcd⁡(a,b)

and

y given x), and then compute a and s = 0 then output "Division by zero" if t := −t (for avoiding negative denominators) if t are two coprime integers such that b divides Z/nZ may be identified with the set n of the result of the addition and the multiplication of integers. An element n. In particular, if n). Thus s and n gives

t by n.

To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of |t| < n. That is, if p is a prime number, and ''d''"}},"i":0}}]}'/>q = p, the field of order d.

A simple algebraic extension p of degree d. The addition in p of the product of polynomials. Thus, to complete the arithmetic in K; this Bézout coefficient (a polynomial generally of positive degree) has thus to be multiplied by the inverse of this element of a is a polynomial.

function inverse(a, p) t := 0; newt := 1 r := p; newr := a while newr ≠ 0 do quotient := r div newr (r, newr) := (newr, r − quotient × newr) (t, newt) := (newt, t − quotient × newt) if degree(r) > 0 then return "Either p is not irreducible or a is a multiple of p" return (1/r) × t

Example

edit

For example, if the polynomial used to define the finite field GF(2) is 8 + ''x''4 + ''x''3 + ''x'' + 1"}},"i":0}}]}'/>p = x + x + x + x + 1, and 6 + ''x''4 + ''x'' + 1"}},"i":0}}]}'/>a = x + x + x + 1 is the element whose inverse is desired, then performing the algorithm results in the computation described in the following table. Let us recall that in fields of order 2, one has −z = z and z + z = 0 for every element z in the field). Since 1 is the only nonzero element of GF(2), the adjustment in the last line of the pseudocode is not needed.

step	quotient	r, newr	s, news	t, newt
		8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1"}},"i":0}}]}'/>p = x + x + x + x + 1	1	0
		6</sup> + ''x''<sup>4</sup> + ''x'' + 1"}},"i":0}}]}'/>a = x + x + x + 1	0	1
1	2</sup> + 1"}},"i":0}}]}'/>x + 1	2</sup> = ''p'' − ''a'' (''x''<sup>2</sup> + 1)"}},"i":0}}]}'/>x = p − a (x + 1)	1	2</sup> + 1 = 0 − 1 · (''x''<sup>2</sup> + 1)"}},"i":0}}]}'/>x + 1 = 0 − 1 · (x + 1)
2	4</sup> + ''x''<sup>2</sup>"}},"i":0}}]}'/>x + x	2</sup> (''x''<sup>4</sup> + ''x''<sup>2</sup>)"}},"i":0}}]}'/>x + 1 = a − x (x + x)	4</sup>+''x''<sup>2</sup> = 0 − 1(''x''<sup>4</sup>+''x''<sup>2</sup>)"}},"i":0}}]}'/>x+x = 0 − 1(x+x)	6</sup> + ''x''<sup>2</sup> + 1 = 1 − (''x''<sup>4</sup> + ''x''<sup>2</sup>) (''x''<sup>2</sup> + 1)"}},"i":0}}]}'/>x + x + 1 = 1 − (x + x) (x + 1)
3	x+x+x+x+1 = 1 − (x +1)(x + x)	7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'' = (''x''<sup>2</sup> + 1) − (''x'' + 1) (''x''<sup>6</sup> + ''x''<sup>2</sup> + 1)"}},"i":0}}]}'/>x + x + x + x = (x + 1) − (x + 1) (x + x + 1)
4	6</sup> + ''x''<sup>4</sup> + ''x'' + 1 = (''x''<sup>4</sup>+''x''<sup>2</sup>) − (''x''+1)(''x''<sup>5</sup>+''x''<sup>4</sup>+''x''<sup>3</sup>+''x''<sup>2</sup>+1)"}},"i":0}}]}"/>x + x + x + 1 = (x+x) − (x+1)(x+x+x+x+1)

Thus, the inverse is 7 + ''x''6 + ''x''3 + ''x''"}},"i":0}}]}'/>x + x + x + x, as can be confirmed by multiplying the two elements together, and taking the remainder by d=gcd⁡(a,b,c). By definition of gcd b. Thus d is a divisor of j. Let ud|a,b,c but since ud=gcd⁡(gcd⁡(a,b),c) the result is proven.

So if y such that gcd⁡(a1,a2,…,an)=gcd⁡(a1,gcd⁡(a2,gcd⁡(a3,…,gcd⁡(an−1,an))),…),

with the equations following directly.