NationMaster - Encyclopedia: Extended Euclidean algorithm

The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y in Bézout's identity In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... In number theory, BÃ©zouts identity, named after Ã‰tienne BÃ©zout, is a linear diophantine equation. ...

$ax + by = gcd(a, b). ,$

(Typically either x or y is negative).

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b. Coprime - Wikipedia /**/ @import /skins-1. ... The modular multiplicative inverse of a number n modulo p is a number m such that n-1 m (mod p). ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value â€” the modulus. ...

1 Informal formulation of the algorithm
2 Formal description of the algorithm
- 2.1 Iterative method
- 2.2 Recursive method
  - 2.2.1 Proof of correctness
3 Computing a multiplicative inverse in a finite field
4 References
5 See also
6 External links

Informal formulation of the algorithm

Dividend	Divisor	Quotient	Remainder
120	23	5	5
23	5	4	3
5	3	1	2
3	2	1	1
2	1	2	0

It is assumed that the reader is already familiar with Euclid's algorithm. The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...

To illustrate the extension of the Euclid's algorithm, consider the computation of gcd(120, 23), which is shown on the table on the left. Notice that the quotient in each division is recorded as well alongside the remainder.

In this case, the remainder in the last line (which is 0) indicates that the gcd is 1; that is, 120 and 23 are coprime (also called relatively prime). For the sake of simplicity, the example chosen is a coprime pair; but the more general case of gcd other than 1 also works similarly. Coprime - Wikipedia /**/ @import /skins-1. ...

There are two methods to proceed, both using the division algorithm, which will be discussed separately. The division algorithm is a theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. ...

The iterative method

This method solves the required equation with the sum replaced by the remainders in each step of the algorithm, which is larger than their gcd, but are decreasing in magnitude, and so will eventually become the required equation. To start with, express each line from the last table with the division algorithm, focusing on the remainder: The division algorithm is a theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. ...

Remainder	=	Dividend	-	Quotient	×	Divisor
5	=	120	-	5	×	23
3	=	23	-	4	×	5
2	=	5	-	1	×	3
1	=	3	-	1	×	2
0	=	2	-	2	×	1

The first line fits the pattern of the original equation, with 120 and 23 as the terms. However from the second line onwards, the terms are decreasing. To proceed, observe that by nature of the Euclidean algorithm:

In each line, the divisor is the remainder of the previous line
The dividend is the previous line's divisor, which is then remainder of its previous line(that is, remainder from two lines up)

Thus the terms can be substituted with the previous two line. By mathematical induction, we can then represent each remainder as sum of multiples of the two original numbers, one after another. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...

Corresponding to this example, notice the divisor on the third line, 3, is the same as the remainder on the second line. Further, the dividend on the third line, 5, is the same as the divisor on the second line, and the remainder on the first line.

In the inductive method, the remainder at each step is written in terms of the integers a and b.

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

The first line already in the required form.
In the second line, substitute 5 with the first line.
In the third line, substitute 5 and 3 with the first and second line.
In the fourth line, substitute 3 and 2 with the second and third line.

The last line reads 1 = −9×120 + 47×23, which is the required solution: x = −9 and y = 47.

This also means that −9 is the multiplicative inverse of 120 modulo 23, and that 47 is the multiplicative inverse of 23 modulo 120. Restating it using mathematical expression: The reciprocal function: y = 1/x. ...

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

The recursive method

This method attempts to solve the original equation directly, by reducing the dividend and divisor gradually, from the first line to the last line, which can then be substituted with trivial value and work backward to obtain the solution.

Consider the original equation:

120	x	+	23	y	=	1
(5×23+5)	x	+	23	y	=	1
23	(5x+y)	+	5	x	=	1
...
1	a	+	0	b	=	1

Notice that the equation remains unchanged after decomposing the original dividend in terms of the divisor plus a remainder, and then regrouping terms. If we have a solution to the equation in the second line, then we can work backward to find x and y as required. Although we don't have the solution yet to the second line, notice how the magnitude of the terms decreased (120 and 23 to 23 and 5). Hence, if we keep applying this, eventually we'll reach the last line, which obviously has (1,0) as a trivial solution. Then we can work backward and gradually find out x and y.

Dividend	=	Quotient	x	Divisor	+	Remainder
120	=	5	x	23	+	5
23	=	4	x	5	+	3
...

For the purpose of explaining this method, the full working will not be shown. Instead some of the repeating steps will be described to demonstrate the principle behind this method.

Start by rewriting each line from the first table with division algorithm, focusing on the dividend this time (because we'll be substituting the dividend).

120	x₀	+	23	y₀	=	1
(5×23+5)	x₀	+	23	y₀	=	1
23	(5x₀+y₀)	+	5	x₀	=	1
23	x₁	+	5	y₁	=	1
(4×5+3)	x₁	+	5	y₁	=	1
5	(4x₁+y₁)	+	3	x₁	=	1
5	x₂	+	3	y₂	=	1

Assume that we were given x₂=2 and y₂=-3 already, which is indeed a valid solution.
x₁=y₂=-3
Solve 4x₁+y₁=x₂ by substituting x₁=-3, which gives y₁=2-4(-3)=14
x₀=y₁=14
Solve 5x₀+y₀=x₁ by substituting x₀=14, so y₀=-3-5(14)=-73

The table method

The table method is probably the simplest method to carry out with a pencil and paper. It is similar to the recursive method, although it does not directly require algebra to use and only requires working in one direction. The main idea is to think of the equation chain $gcd(x, y), gcd(y, xmod y), dots, gcd(z, 1)$ as a sequence of divisors $x, y, xmod y, dots, 1$ . In the running example we have the sequence 120, 23, 5, 3, 2, 1. Any element in this chain can be written as a linear combination of the original $x$ and $y$ , most notably, the last element, $gcd(x, y)$ , can be written in this way. The table method involves keeping a table of each divisor, written as a linear combination. The algorithm starts with the table as follows:

a	b	d
1	0	120
0	1	23

The elements in the $d$ column of the table will be the divisors in the sequence. Each $d i$ can be represented as the linear combination $d_i = a_i cdot x + b_i cdot y$ . The $a$ and $b$ values are obvious for the first two rows of the table, which represent $x$ and $y$ themselves. To compute $d i$ for any $i > 2$ , notice that $d_i = d_{i-2} mod d_{i-1}$ . Suppose $d_i = d_{i-2} - k cdot d_{i-1}$ . Then it must be that $a_i = a_{i-2} - k cdot a_{i-1}$ and $b_i = b_{i-2} - k cdot b_{i-1}$ . This is easy to verify algebraically with a simple substitution.

Actually carrying out the table method though is simpler than the above equations would indicate. To find the third row of the table in the example, just notice that 120 divided by 23 goes 5 times plus a remainder. This gives us k, the multiplying factor for this row. Now, each value in the table is the value two rows above it, minus 5 times the value immediately above it. This correctly leads to $a_3 = 1 - 5 cdot 0 = 1$ , $b_3 = 0 - 5 cdot 1 = -5$ , and $d_3 = 1 cdot 120 - 5 cdot 23 = 5$ . After repeating this method to find each line of the table, the final values for $a$ and $b$ will solve $ax + by = gcd(x, y),$ :

a	b	d
1	0	120
0	1	23
1	-5	5
-4	21	3
5	-26	2
-9	47	1

This method is simple, requiring only the repeated application of one rule, and leaves the answer in the final row of the table with no backtracking. Note also that if you end up with a negative number as the answer for the factor of, in this case b, you will then need to add a in order to make it work as a modular inverse (instead of just taking the absolute value of b). I.e. if it returns a negative number, don't just flip the sign, but add in the other number to make it work. Otherwise it will give you the modular inverse yielding negative one.

Formal description of the algorithm

Iterative method

By routine algebra of expanding and grouping like terms (refer to last section), the following algorithm for iterative method is obtained:

Apply Euclidean algorithm, and let q_n(n starts from 1) be a finite list of quotients in the division.
Initialize x₀, x₁ as 1, 0, and y₀, y₁ as 0,1 respectively.
1. Then for each i so long as q_i is defined,
2. Compute x_i+1= x_i-1- q_ix_i
3. Compute y_i+1= y_i-1- q_iy_i
4. Repeat the above after incrementing i by 1.
The answers are the second-to-last of x_n and y_n.

Pseudocode for this method is shown below:

 function extended_gcd(a, b) x := 0 lastx := 1 y := 1 lasty := 0 while b ≠ 0 temp := b quotient := a div b b := a mod b a := temp temp := x x := lastx-quotient*x lastx := temp temp := y y := lasty-quotient*y lasty := temp return {lastx, lasty, a}

Recursive method

Solving the general case of the equation in the last corresponding section, the following algorithm results:

If a is divisible by b, the algorithm ends and return the trivial solution x=0, y=1.
Otherwise, repeat the algorithm with b and a modulus b, storing the solution as x' and y'.
Then, the solution to the current equation is x=y', and y = x' minus y' times quotient of a divided by b

Which can be directly translated to this pseudocode:

 function extended_gcd(a, b) if a mod b = 0 return {0, 1} else temp := extended_gcd(b, a mod b) x := first(temp) y := last(temp) return {y, x-y*(a div b)}

Proof of correctness

Let d be the gcd of a and b. We wish to prove that a*x + b*y = d.

If b evenly divides a (i.e. a mod b = 0),
- then d is b and a*0 + b*1 = d.
- So x and y are 0 and 1.
Otherwise given the recursive call we know that b*x + (a mod b) * y = d,
- then b*x - b*(a div b)*y + (a mod b) * y + b*(a div b)*y= d,
- and b*(x - (a div b)*y) + a*y=d.
- So the new x and y are y and x - (a div b)*y.

See the Euclidean algorithm for the proof that the gcd(a,b) = gcd(b,a mod b) which this proof depends on in the recursive call step. In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ...

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. The reciprocal function: y = 1/x. ... In abstract algebra, a finite field or Galois field (so named in honor of Ã‰variste Galois) is a field that contains only finitely many elements. ...

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. NOTE: remainder() and quotient() are functions different from the arrays remainder[ ] and quotient[ ]. remainder() refers to the remainder when two numbers are divided, and quotient() refers to the integer quotient when two numbers are divided. For example, remainder(5/3) = 2 and quotient(5/3) = 1. Equivalent operators in the C language are % and / respectively.

pseudocode: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 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]

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 its own additive inverse in GF(2⁸). In abstract algebra, a finite field or Galois field (so named in honor of Evariste Galois) is a field that contains only finitely many elements. ...

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: In computing, endianness is the byte (and sometimes bit) ordering in memory used to represent some kind of data. ... In mathematics and computer science, hexadecimal, base-16, or simply hex, is a numeral system with a radix, or base, of 16, usually written using the symbols 0â€“9 and Aâ€“F, or aâ€“f. ...

i	remainder[i]	quotient[i]	auxiliary[i]
1	x⁸ + x⁴ + x³ + x + 1		0
2	x⁶ + x⁴ + x + 1		1
3	x²	x² + 1	x² + 1
4	x + 1	x⁴ + x²	x⁶ + x⁴ + x⁴ + x² + 1
5	1	x + 1	x⁷ + x⁶ + x³ + x² + x² + 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. Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... Arithmetic in a finite field is different from standard integer arithmetic. ...

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

A php implementation of the Extended Euclidean Algorithm showing line-by-line working and outputs
A javascript implementation 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)

Categories: Number theoretic algorithms | Articles with example pseudocode

Results from FactBites:

PlanetMath: fast Euclidean algorithm (222 words)
	The algorithm can also be used to compute any particular pair of coefficients from the Extended Euclidean Algorithm, although computing every pair of coefficients would involve
	The full algorithm, and a comprehensive runtime analysis is given in “Modern Computer Algebra” by von zur Gathen and Gerhard.
	This is version 4 of fast Euclidean algorithm, born on 2004-07-22, modified 2005-04-14.

PlanetMath: Berlekamp-Massey algorithm (0 words)
	The Berlekamp-Massey algorithm is used for finding the minimal polynomial of a linearly recurrent sequence.
	The algorithm itself is presented at the end of this article.
	This is version 4 of Berlekamp-Massey algorithm, born on 2004-07-22, modified 2005-04-14.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Informal formulation of the algorithm GA_googleFillSlot("encyclopedia_square");