Extended Euclidean algorithm

From Exampleproblems

The extended Euclidean algorithm is an algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers a and b, as well as integers x and y such that

(This equation is known as Bezout's identity.) The algorithm is essentially the same as the Euclidean algorithm, but keeps track of more information during the computation in order to find x and y as above.

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the multiplicative inverse of a modulo b.

Contents 1 Calculating a gcd (and multiplicative inverse) 2 Pseudocode for finding x and y 3 Computing a multiplicative inverse in a finite field 3.1 Pseudocode 3.2 Note 3.3 Example 4 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

In this case, the remainder in the second-to-last line indicates that the gcd 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, and also 47 is the multiplicative inverse of 23 modulo 120. This means that

−9 × 120 ≡ 1 (mod 23) and also 47 × 23 ≡ 1 (mod 120).

.

Pseudocode for finding x and y

usage: f(a, b, 0, 0, true)

• a and b are the values used in gcd(a, b)
• a' and b' are the previous a and b values from the preceding equation. They can be any values when f is called
• for a = qb + r, a quotient b returns q and a mod b returns r.
• the boolean variable first prevents the recursion from recursing back up too far. In general, the n^th call of f will return a pair of integers x and y such that ax + by = gcd(a,b) for a and b of the (n-1)^th call of f. When we get back to the 1^st recursive call, therefore, we need the result from the 2^nd recursive call.

Example function trace:

Call 1

f(25, 7, 0, 0, true) =

f(7, 4, 25, 7, false) = {-5, 18}

Call 2	f(7, 4, 25, 7, false) =	{-5, 3 - -5(3)} = {-5, 18}	25(-5) + 7(18) = 1 = gcd(25,7) where a = 25 and b = 7 are from call 1
	temp =	f(4, 3, 7, 4, false) = {3, -5}
	x =	3
	y =	-5

Call 3	f(4, 3, 7, 4, false) =	{3, -2 - 3(1)} = {3, -5}	7(3) + 4(-5) = 1 = gcd(7,4) where a = 7 and b = 4 are from call 2
	temp =	f(3, 1, 4, 3, false) = {-2, 3}
	x =	-2
	y =	3

Call 4	f(3, 1, 4, 3, false) =	{-2, 1 - -2(1)} = {-2, 3}	4(-2) + 3(3) = 1 = gcd(4,3) where a = 4 and b = 3 are from call 3
	temp =	f(1, 0, 3, 1, false) = {1, -2}
	x =	1
	y =	-2

Call 5

f(1, 0, 3, 1, false) =

{1, 1-(3)} = {1, -2}

3(1) + 1(-2) = 1 = gcd(3,1) where a = 3 and b = 1 are from call 4

f(a, b, a', b', first)
{
	if(b != 0)
	{
		if(first & a mod b != 1)
		{
			return f(b, a mod b, a, b, false)
		}
		else if(first & a mod b = 1)
		{
			return {1, -(a quotient b)}
		}
		else
		{
			if(a mod b = 1)
			{
				return {-(a quotient b), 1+(a' quotient b')(a quotient b)}
			}
			else
			{
				temp = f(b, a mod b, a, b, false)
				x = first(temp)
				y = last(temp)
				return {y, x - y(a' quotient b')}
			}
		}
	}
	else
	{
		return {1, 1 - (a' quotient b')}
	}
}

There is another algorithm that is more elegant, yet slightly less intuitive. It takes the algebraic by-hand method of finding x and y one step further. Consider the example in the previous section:

gcd(120,23): 120 = 5*23 + 5
  gcd(23,5):  23 = 4*5  + 3
   gcd(5,3):   5 = 3*1  + 2
   gcd(3,2):   3 = 2*1  + 1
   gcd(2,1):   2 = 2*1  + 0
   gcd(1,0) =  1 = 1*1  + 0 --> x = 1 y = 0 when a = 1 b = 0

The last step in this trace is present in every application of the Euclidian algorithm in a more general form: x = 1 and y = 0 when a = c and b = 0, where c is a positive integer (c = c*1 + 0). The function g makes use of this to avoid the need to keep track of the previous a and b values.

g(a, b)
{
	if(b = 0)
		return {1, 0}
	else
	{
		temp = g(b, a mod b)
		x = first(temp)
		y = last(temp)
		return {y, x-y(a quotient b)}
	}
}

Computing a multiplicative inverse in a finite field

The extended Euclidean 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(jh)
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]

Note

The minus sign is not necessary for some finite fields in the step

auxiliary[i] := -quotient[i] * auxiliary[i-1] + auxiliary[i-2]

This is true since in the finite field GF(2⁸), for instance, addition and subtraction are the same. In other words, 1 is it's own additive inverse in GF(2⁸).

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

Note: Addition in a binary finite field is XOR.

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

External links

• A php implimentation of the Extended Euclidean Algorithm showing line-by-line working and outputs
• A javascript implimentation of the Extended Euclidean Algorithm shown above
• How to use the algorithm by hand
• Extended Euclidean Algorithm Applet
• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)
• Source of a C++ program which calculates the multiplicative inverse.
• Compiled version of the C++ program mentioned above.de:Erweiterter euklidischer Algorithmus

fr:Algorithme d'Euclide étendu