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)/Highest Common Factor(HCF), 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 coprime: x is then the multiplicative inverse of a modulo b.

Contents

1 Calculating a gcd/HCF (and multiplicative inverse) 2 Algebraic formulation 2.1 Javascript implementation 3 Computing a multiplicative inverse in a finite field 3.1 Pseudocode 3.2 Example 4 External links

Calculating a gcd/HCF (and multiplicative inverse)

Consider as an example the computation of gcd/HCF(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

In this case, the remainder in the second-to-last line indicates that the gcd/HCF is 1; that is, 120 and 23 are coprime (also called relatively prime). Now do a little algebra on each of the above lines:

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

Now observe that the first line contains multiples of 120 and 23. Also, the rightmost values are in each case the remainders listed on the previous line, and the left side of the differences are the residues from two lines up. We can thus progressively calculate each successive remainder as sums of products of our two original values.

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

Algebraic formulation

Let a and b be integers such that a ≥ b > 0. Define mod(a, b) as the positive remainder such that 0 ≤ mod(a, b) < b. Define the sequences

<math>\begin{matrix}r_0 &=& a& s_0 &=& 1 & t_0 &=& 0 \\

                    r_1 &=& b& s_1 &=& 0 & t_1 &=& 1 \\
                    r_i &=& mod(r_{i-2}, r_{i-1})& s_i &=& s_{i-2} - q_{i-1} s_{i-1}& t_i &=& t_{i-2} - q_{i-1} t_{i-1} \end{matrix}<math>

Where q_i is a quotient defined as

<math>q_i = \lfloor r_{i-1}/r_{i}\rfloor<math>

Choose the smallest n such that <math>r_{n+1}=0<math>. Then:

<math>\mbox{gcd/HCF}(a, b) = r_n = as_n + bt_n.<math>

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/HCF(" + 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]

/********************** Could somebody check this?

is the minus sign necessary in the step auxiliary[i] := -quotient[i] * auxiliary[i-1] + auxiliary[i-2] ?

i've tried it ignoring the sign and it works

/**********************

Example

For example, if the polynomial used to define the finite field GF(2⁸) is f(x) = x⁸ + x⁴ + x³ + x + 1, and x⁶ + x⁴ + 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	x8 + x4 + x3 + x + 1		0
2	x6 + x4 + x + 1		1
3	x2	x2 + 1	x2 + 1
4	x + 1	x4 + x2	x6 + x4 + x4 + x2 + 1
5	1	x + 1	x7 + x6 + x3 + x2 + x2 + x + 1 + 1

Thus, the inverse is x⁷ + x⁶ + x³ + x = {CA}, as can be confirmed by multiplying the two elements together.

External links

• How to use the algorithm by hand (http://www.millersv.edu/~bikenaga/absalg/exteuc/exteucex.html)
• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) (http://mathforum.org/library/drmath/view/51675.html)de:Erweiterter euklidischer Algorithmus

fr:Algorithme d'Euclide étendu