# Extended Euclidean algorithm

The **extended Euclidean algorithm** is a version of the Euclidean algorithm; its input are two integers *a* and *b* and the algorithm computes their greatest common divisor (gcd) as well as integers *x* and *y* such that *ax* + *by* = gcd(*a*, *b*). This works because the steps of Euclid's algorithm always deal with sums of multiples of *a* and *b*.

The equation *ax* + *by* = gcd(*a*, *b*) is particularly useful when *a* and *b* are relatively prime: *x* is then the multiplicative inverse of *a* modulo *b*.

Table of contents |

2 Computing a multiplicative inverse in a finite field 3 External links |

## Calculating a gcd (and multiplicative inverse)

Consider as an example the computation of gcd(120, 23) with Euclid's algorithm:

120 / 23 = 5 r 5 23 / 5 = 4 r 3 5 / 3 = 1 r 2 3 / 2 = 1 r 1 2 / 1 = 2 r 0

120 / 23 = 5 r 5 => 5 = 120 - 5*23 23 / 5 = 4 r 3 => 3 = 23 - 4*5 5 / 3 = 1 r 2 => 2 = 5 - 1*3 3 / 2 = 1 r 1 => 1 = 3 - 1*2 2 / 1 = 2 r 0 => 0 = 2 - 2*1

Here we rewrite the second equations in the above table:

5 = 120 - 5*23 = 1*120 - 5*23 3 = 23 - 4*5 = 1*23 - 4*(1*120 - 5*23) = -4*120 + 21*23 2 = 5 - 1*3 = (1*120 - 5*23) - 1*(-4*120 + 21*23) = 5*120 - 26*23 1 = 3 - 1*2 = (-4*120 + 21*23) - 1*(5*120 - 26*23) = -9*120 + 47*23

Notice that the last line says that 1 = −9×120 + 47×23, which is what we wanted: *x* = −9 and *y* = 47.

This means that −9 is the multiplicative inverse of 120 modulo 23, because 1 = −9 × 120 (mod 23).

### Javascript implementation

Here is a JavaScript implementation of the Extended Euclidean algorithm which should work in most browsers:

// This program works only for non-negative inputs. // Get data from user and convert strings to integers. var a = parseInt(prompt("Enter non-negative value for a",0)) var b = parseInt(prompt("Enter non-negative value for b",0))// Save original values. a0 = a; b0 = b;

// Initializations. We maintain the invariant p*a0 + q*b0 = a and r*a0 + s*b0 = b. p = 1; q = 0; r = 0; s = 1;

// The algorithm: while (b != 0) {

c = a % b; quot = Math.floor(a/b); //Javascript doesn't have an integer division operator a = b; b = c; new_r = p - quot * r; new_s = q - quot * s; p = r; q = s; r = new_r; s = new_s;}// Show result.

alert("gcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 +

"+(" + q + ")*" + b0 + "=" + a)

## Computing a multiplicative inverse in a finite field

The extended Euclidian algorithm can also be used to calculate the multiplicative inverse in a finite field.

### Pseudocode

Given the irreducible polynomial *f*(*x*) used to define the finite field, and the element *a*(*x*) whose inverse is desired, then a form of the algorithm suitable for determining the inverse is given by the following pseudocode:

remainder[1] =f(x) remainder[2] =a(x) auxiliary[1] = 0 auxiliary[2] = 1 i = 2 do while remainder[i] <> 1 i = i + 1 remainder[i] =remainder(remainder[i-2] / remainder[i-1]) quotient[i] =quotient(remainder[i-2] / remainder[i-1]) auxiliary[i] = quotient[i] * auxiliary[i-1] + auxiliary[i-2] inverse = auxiliary[i]

### Example

For example, if the polynomial used to define the finite field GF(2^{8}) is *f*(*x*) = *x*^{8} + *x*^{4} + *x*^{3} + *x* + 1, and *x*^{6} + *x*^{4} + *x* + 1 = {53} in big-endian hexadecimal notation, is the element whose inverse is desired, then performing the algorithm results in the following:

i | remainder[i] | quotient[i] | auxiliary[i] |
---|---|---|---|

1 | x^{8} + x^{4} + x^{3} + x + 1 |
0 | |

2 | x^{6} + x^{4} + x + 1 |
1 | |

3 | x^{2} |
x^{2} + 1 |
x^{2} + 1 |

4 | x + 1 |
x^{4} + x^{2} |
x^{6} + x^{4} + x^{4} + x^{2} + 1 |

5 | 1 | x + 1 |
x^{7} + x^{6} + x^{3} + x^{2} + x^{2} + x + |

*Note: Addition in a finite field is XOR.*

Thus, the inverse is *x*^{7} + *x*^{6} + *x*^{3} + *x* = {CA}, as can be confirmed by multiplying the two elements together.