 Cryptography >  Tools > The Extended Euclidean Algorithm (45 min.) Objectives: 1) Understand the Extended Euclidean Algorithm to determine the inverse of a given integer.  2) Learn how to program it.

The Extended Euclidean Algorithm

I will demonstrate to you how the Extended Euclidean Algorithm finds the inverse of an integer for any given modulus. This method is the most efficient way to compute a modular inverse. It involves two steps:

Step 1: We perform the Euclidean Algorithm ("Forward").
Step 2: We reverse the Euclidean Algorithm. ("Backward")

Step 1:
Let's start off with a simple example: To find the inverse of 15 mod 26, we first have to perform the Euclidean Algorithm "Forward". Here, we divide repeatedly until we obtain a remainder of 0:

 26 = 1 * 15 +      11 15 = 1 * 11 +      4 11 = 2 * 4 +      3 4 = 1 * 3 +      1 3 = 3 * 1 + 0

The remainder of the 2nd to last line, 1, yields the gcd of 15 and 26. We can drop the irrelevant last equation.

Step 2: "Euclidean Algorithm Backwards"
We now substitute backwards until the gcd(26,15)=1 is expressed as a linear combination of 26 and 15. To do so, we first isolate each of the four remainders: Starting with the last equation:

 1 = 4 - 3 3 = 11 - 2 * 4 4 = 15 - 11 11=26 -15

Back-substituting these four identities enables us to express the gcd = 1 in terms of 26 and 15 n such as:
gcd = 1 = x*26 + y*15 with x and y being integers.
The inverse of 15 is y and we are done. Let's do it.

 1 = 4 -  3

Replacing 3 by 11 - 2*4 yields:

 1 = 4 -  (11 - 2*4) = 3 * 4  - 11

Next, I replace 4 by 15-11:

 1 = 3 * (15-11)  - 11 = 3*15 - 4*11

I finally replace 11 by the 26-15:

 1 =  3*15 - 4*(26-15) 1 = 7*15 - 4*26

This is it. Let's first verify that 7*15 - 4*26 equals 1:
7*15 - 4*26 = 105 - 104 = 1. Correct.
7 is the desired of 15 since the last equation can be read as
1 = 7*15 mod 26.
To verified that 7 is the inverse of 15: 7*15=105=1 mod 26.

Two Important Observations:

1. By reversing the steps in the Euclidean Algorithm we can always express the gcd of the integers a and b in the form

gcd = x*a + y*b
with two integers x and y.

Consequently, if a and b have a greatest common divisor different from 1 (that is the gcd(a,b) is not 1) a does not have an inverse mod b. I.e. 14 has no inverse mod 26. However, it has mod 27, namely 2. (How do I know?) Therefore, we first execute the Euclidean Algorithm to check if a and the modulus b have a greatest common divisor of 1. Only in that case, the back substitutions yield an inverse.

2. Having performed the back substitutions, we may end up with a negative value for the inverse. I.e. to find the inverse of 23 mod 26, we first execute the Euclidean Algorithm as follows:

 26 = 1 * 23 +      3 23 = 7 * 3 +       2 3 = 1 * 2 +      1 2 = 2 * 1 + 0.

Back-substitutions yield:

 1 = 3 - 2 = 3 - (23 - 7*3) = 8*3 - 23 = 8*(26-23) - 23 = 8*26 - 9*23

Is 9 the inverse of 23 mod 26? It can not be since 9*23 = 207 and 207 = 25 = -1 MOD 26 which is not 1.
The correct inverse is -9. This can be better seen if I rewrite the last equation as follows:
1 = 8*26 + (- 9)*23.
Since we want the inverse to be a positive number less than the modulus 26 we simply add 26 to -9 yielding 17 as our desired inverse:
Check:  17*23 = 391 = 260 + 130 + 1 = 1 mod 26.

Conclusion: Whenever the coefficient x is negative, we have to add the modulus b to it in order to obtain the proper inverse as our decoding key.

Use the Back-Substitution for the following 3 exercises:

Exercise 1: Find the inverse of 5 mod 26.   21

Exercise 2: Find the inverse of 19 mod 26.   11

Exercise 3: Find the inverse of 13 mod 22.    17

The above procedure works well, however, it is quite time consuming because of the back substitutions we have to make. It is possible to reduce the amount of computation involved in finding x and y by doing some auxiliary computations when performing step 1. No back substitutions will be necessary. This procedure is known as the Extended Euclidean Algorithm which I explain to you now.

### The Extended Euclidean Algorithm finds the Modular Inverse

The following explanations are more of a technical nature. Read them if intend to implement the Euclidean Algorithm, skip them if you don't and go straight to the bottom of this page to view the Extended Euclidean Algorithm in action.

Notice that we do not have to calculate the value of y in gcd = x*a + y*b since x yields the inverse of a mod b. We first have to number the steps of the Euclidean algorithm since we will make use of the quotients q. Starting with step 0, the quotient obtained at step i will be denoted as qi. How are these values used? They are part of the formula

xi = (xi-2 - [xi-1*qi-2]) (mod b)

which is carried from step 2 on of the Euclidean algorithm.  If we perform these calculations for one step beyond the last step of the Euclidean algorithm it will yield the desired inverse. In step 0 and step 1 we don't compute anything since the x-values are given: x0 = 0 and x1 = 1

As usual, let's take a look at a simple example:

#### Say, we want to find the inverse of 15 mod 26.

 Step 0: 26 = 1*15 + 11 x0 = 0 Step 1: 15 = 1*11 + 4 x1 = 1 Step i: From step 2 on we compute: xi = (xi-2 - [xi-1 * qi-2]) mod 26. Step 2: 11 = 2*4 + 3 x2 = (x0 - [x1 * q0])       = 0 - 1*1 mod 26 = 25 Step 3: 4 = 1*3 + 1 x3 = (x1 - [x2 * q1])     = 1 - 25*1 = -24 mod 26 = 2 Step 4: 3 = 3*1 + 0 x4 = (x2 - [x3 * q2])      = 25 - 2*2 mod 26 = 21 x5 = (x3 - [x2 * q3])          = 2 - 21*1 = -19 mod 26 = 7

Check: 15*7 = 105 = 1 + 4*26 = 1 mod 26. Thus, 7 is the inverse of 15 mod 26.

Exercise 4:
Find the inverse of 5 mod 26 using the Extended Euclidean Algorithm by hand.
21. Check below.

Exercise 5:
Find the inverse of 19 mod 26 using the Extended Euclidean Algorithm by hand.
11. Check below.

Exercise 6:
Find the inverse of 13 mod 22 using the Extended Euclidean Algorithm by hand.
17. Check below.

Again, the Extended Euclidean Algorithm should be performed by a computer as it is very easy to implement and it yields the answer quickly. Below you can compute the inverse of any an integers a mod b. Additionally, you can observe the steps involved that lead to the final answer. Thus, enter the two integers a and b followed by hitting the "Compute Inverse" button.
1) Enter a = - the smaller integer
2) Enter (modulus) b = - the larger integer Euclid of Alexandria (325-265 BC)  was the most prominent Mathematician at his time. He summarized his discoveries in "The Elements". Here is an excerpt: 1. There are infinitely many primes. 2. Euclidean Geometry. 3. Euclidean Algorithm.

Related web sources:

Cut-the-knot.com
(Play the Euclid game here)

Encarta.com

Britannica.com

Glossary

PBS Online

Introduction to Cryptography

Enigma and the Codebreakers

Enigma History

Enigma Emulator

The Inverse can be read off as the last computed x value in the last line of the right column:
top