# Extended Euclidean algorithm

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: $ax + by = gcd\left(a, b\right). ,$

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

Informal formulation of the algorithm

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.

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\left(x, y\right), gcd\left(y, xmod y\right), dots, gcd\left(z, 1\right)$ 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\left(x, y\right)$, 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:

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_\left\{i-2\right\} mod d_\left\{i-1\right\}$. Suppose $d_i = d_\left\{i-2\right\} - k cdot d_\left\{i-1\right\}$. Then it must be that $a_i = a_\left\{i-2\right\} - k cdot a_\left\{i-1\right\}$ and $b_i = b_\left\{i-2\right\} - k cdot b_\left\{i-1\right\}$. 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 k 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 (note that the remainder written in the table and the multiplying factor are two different numbers!), the final values for $a$ and $b$ will solve $ax + by = gcd\left(x, y\right),$:

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 the modulus 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 qn(n starts from 1) be a finite list of quotients in the division.
# Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
## Then for each i so long as qi is defined,
## Compute xi+1= xi-1- qixi
## Compute yi+1= yi-1- qiyi
## Repeat the above after incrementing i by 1.
# The answers are the second-to-last of xn and yn.

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 {x, y} := extended_gcd(b, a mod b) 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.

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

remainder [1] := "f"(x) remainder [2] := "a"(x) auxiliary [1] := 0 auxiliary [2] := 1 i := 2 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(28), for instance, addition and subtraction are the same. In other words, 1 is its own additive inverse in GF(28). This occurs in any finite field GF(2n), where n is an integer.

Example

For example, if the polynomial used to define the finite field GF(28) 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:

iremainder [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" + 1 + 1
:"Note: Addition in a binary 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.

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&ndash;861 of section 31.2: Greatest common divisor.

ee also

* Bézout's identity

* [http://marauder.millersville.edu/~bikenaga/absalg/exteuc/exteucex.html How to use the algorithm by hand]
* [http://marauder.millersville.edu/~bikenaga/absalg/euc/euclidex.html How to use the algorithm by hand]
* [http://banach.millersville.edu/~bob/math478/ExtendedEuclideanAlgorithmApplet.html Extended Euclidean Algorithm Applet]
* [http://mathforum.org/library/drmath/view/51675.html Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)]
* [http://www.cs.utoronto.ca/~trebla/ExtendedEuclid.txt A simple explanation of the Extended Euclidean Algorithm]
* [http://www.informationsuebertragung.ch/indexAlgorithmen.html Extended Euclidean Algorithm Applet] (Deutsch)

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Euclidean algorithm — In number theory, the Euclidean algorithm (also called Euclid s algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). Its major significance is that it does… …   Wikipedia

• Euclidean domain — In abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm applies. A Euclidean domain is a specific type of integral domain, and can be characterized by the following (not… …   Wikipedia

• Euclidean — List of topics named after Euclid (Euclidean or, less commonly, Euclidian) *Euclidean space *Euclidean geometry *Euclid s Elements *Euclidean domain *Euclidean distance *Euclidean ball *Euclidean algorithm *Euclidean distance map *Extended… …   Wikipedia

• Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

• Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

• Binary GCD algorithm — The binary GCD algorithm is an algorithm which computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which… …   Wikipedia

• Digital Signature Algorithm — The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature… …   Wikipedia

• Euclidean geometry — A Greek mathematician performing a geometric construction with a compass, from The School of Athens by Raphael. Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his… …   Wikipedia

• Lehmer's GCD algorithm — Lehmer s GCD algorithm, named after Derrick Henry Lehmer, is a rather fast GCD algorithm, an improvement on the simpler but slower Euclidean algorithm. Algorithm Lehmer noted that that most of the quotients from each step of the division part of… …   Wikipedia

• Cornacchia's algorithm — In computational number theory, Cornacchia s algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1]. Contents 1 The algorithm …   Wikipedia