Euclid's Algorithm

Introduction

I was recently going through the cryptohack challenges when I came across the Greatest Common Divisor (GCD) challenge, this challenge is a novice level challenge where you are expected to code up a function to compute the GCD of two numbers, a link to Euclid's Algorithm was provided as a hint to solve the problem. Normally, as expected I followed the link just to brush up on my understanding, considering that it's something I already knew. Soon after I proceeded to code up the function and then realized I was missing a great deal of what was supposed to be intuitive, that is, I did not properly understand the algorithm as I thought, hence this post.

So what is Euclid's Algorithm? It's an algorithm attributed to 300 B.C. Greek mathematician Euclid, for efficiently computing the greatest common divisor of two numbers, this algorithm has a wide array of uses especially in the field of cryptography. The GCD of any two numbers, for example, 5 and 12, is the largest number that divides both numbers without any remainder. So what Euclid did is come up with a set of steps to solves this problem for any two given numbers.

Naive Euclid's Algorithm

The set of steps proposed by Euclid is as follows:

1. Given a set of two numbers, e.g 5 and 12
2. Subtract the smaller number i.e 5 from the bigger number i.e 12
3. Assign the result of step two (12 - 5 = 7) as the bigger number, overwriting the previous value (i.e 12 will now be replaced by 7, leaving us with 5 and 7 as the new set of numbers)
4. Repeat the process all over again from step one with the new  set of numbers (i.e 5 and 7) until you reach a point where both numbers are equal, when that happens, the number is the GCD of the two initial numbers

The figure below shows this process:

Fig. 1 - Computing the GCD of 12 and 5 which is 1

From Fig. 1 we can see that the GCD of 12 and 5 is 1 i.e is the only number that divides both 12 and 5 without any remainder. Using the above steps you can find the GCD of any two numbers.

The Intuition

Why does this algorithm work? first, remember that every Natural number (i.e {1, 2, 3...}) is divisible by 1, and that's because every natural number from 1 is just a successive increment of 1 as can be seen in Fig. 2

Fig. 2 - Successive increment of two numbers

Also, we know that every number is divisible by itself but not divisible by any number greater than itself i.e 5 is divisible by 5 but not 6 or 7 e.t.c, therefore we can say that the Greatest Divisor (GD) of any given single natural number is itself i.e the GD of 5 is 5, the GD of 7 is 7. So far, we've established the following:

1. Every natural number is divisible by 1
2. A divisor of any natural number must be less than or equal to the natural number
3. The Greatest Divisor of any single Natural number must be itself

Now, given two numbers, if both numbers are equal then they must be the same number i.e if a = 7 and b = 7, then a == b, and from rule 3 above, the greatest divisor of 7 is 7, the easy part. But if both numbers are not equal e.g a = 12 and b = 5, now since the number we seek is a common divisor between the two numbers, then we know from rule 2 that the divisor must be less than or equal to the smaller number, in this case, 5, therefore it is safe to subtract the smaller number from the bigger number since we already know the GCD cannot be found in the larger part of that bigger number, after the subtraction, we are now left with a new set of numbers and we repeat the above process eventually we get to a point where the numbers are equal which in the worst case is 1 and when that happens we use rule 3 to conclude that the number is the GCD of the two given numbers.

Code Implementation

Naive Euclid's Algorithm

Efficient Euclid's Algorithm

But why do we refer to the above algorithm as naive? Well, because if given two numbers where one is significantly greater than the other e.g a = 724 and b = 8032523, then the subtraction will take a long time to converge to the smaller number. So a more efficient version was developed and it works by replacing the greater of the two numbers by the remainder when the greater number is divided by the lesser number and when the remainder of the numbers becomes zero the algorithm terminate and we return the other number

Efficient Euclid's Algorithm

Now, I think I fairly understand Euclid's Algorithm. In the next part of this post, we will dive into the Extended Euclidean Algorithm and probably look at its usefulness in practical cryptography.