Understanding the extended Euclidean algorithm

The Euclidean algorithm finds the greatest common divisor of two numbers a and b. There is an extended version of it that also finds two numbers x and y such that ax + by = gcd(a,b). This is useful when searching for modular multiplicative inverses.

The algorithm is simple, but I’ve never bothered to study why and how it works (a shame, really, but sometimes you have to postpone the understanding of some basic things in order to go on…). Finally I’ve decide to put some thought on it and came up with this (this is not a proof; it’s just some intuitive thinking to grasp the inner workings of the algorithm).

Suppose that you want to compute the extended Euclidean algorithm for a = 14 and b = 101. You can write

14 *   1 + 101 *   0 =  14
14 *   0 + 101 *   1 = 101

Which is obviously true. Now subtract the first equation from the second:

14 *   1 + 101 *   0 =  14
14 *   0 + 101 *   1 - (14 *   1 + 101 *   0) = 101 - 14 ->
14 *  -1 + 101 *   1 = 87

You can repeat this many times before reducing the right-hand 101 in the second equation to the smallest positive value possible. Notice that it’s faster to take the floor(101/14) and subtract the first equation times the result from the second. In this case, we have floor(101/14) = 7. Therefore, replace the last step with:

14 *   1 + 101 *   0 =  14
14 *   0 + 101 *   1 - [7 * (14 *   1 + 101 *   0)] = 101 - [7 * 14] ->
14 *  -7 + 101 *   1 =   3

Now, switch equations, in order to make the first one the one with the smallest right-hand size (you’ll always need to switch):

14 *  -7 + 101 *   1 =   3
14 *   1 + 101 *   0 =  14

And here you are. Just repeat the same step over and over:

14 *  29 + 101 *  -4 =   2
14 *  -7 + 101 *   1 =   3

14 * -36 + 101 *   5 =   1
14 *  29 + 101 *  -4 =   2

14 * 101 + 101 * -14 =   0
14 * -36 + 101 *   5 =   1

When your first equation has right-hand side equal to 0 (this will always happen), the second equation will be ax + by = gcd(a,b)!

As I mentioned, this is useful in order to find modular inverses: to find which number that when multiplied by 14 gives 1 (modulo 101) you run the algorithm as described and finds that it’s -36 (which is 65 modulo 101). That is, 14 * 65 = 910, which when divided by 101, gives remainder 1. Modular inverses are used in many cryptographic applications, such as RSA.

I think I’ll study next the seemingly magical Montgomery reduction (I understand how it works, I have even implemented it, but I still don’t know why the heck it works)…

4 comments

  1. Thanks man for your effort.
    I’m doing a hardware implementation of Shamir’s Secret sharing as a Senior project. This post and the Montgomery one were very helpful.

    Keep it up!

  2. The most intuitive explanation I’ve found for the extended Euclidean algorithm once you know the normal one. Great post!

Leave a comment

Your email address will not be published. Required fields are marked *