Greatest Common Divisor

One of the fundamental tools used in cryptography over the last few decades has been the Greatest Common Divisor (GCD), which is used in the process of generating and verifying RSA encryption keys. This article will walk through a few algorithms to find the answer quickly and efficiently.

What is the Greatest Common Divisor

The greatest common divisor is defined as the largest number that wholly divides two given numbers so that there is no remainer left. For example, the GCD of 12 and 18 is 6 because the numbers 12 and 18 can be divided by 6 without any remainder.

Basic Algorithm

The easiest concept to try when first learning about the greatest common denominator is to iterate over every value that can possibly be a common denominator. It is slow and clunky but it at least works - and computers are fast these days anyway.

function BasicAlgorithm(left: number, right: number) {
    let bestSoFar: number = 1;

    // Iterate over every number until the left or right value is reached
    for (let i: number = 2; i <= Math.min(left, right); i++) {
        if ( left % i === 0 && right % i === 0 ) {
            // Found a new highest value
            bestSoFar = i;
        }
    }
    return bestSoFar;
}

Using the above function, lets test how long things take.

Well that was pretty quick. Unless something went drastically wrong you should see < 1ms of time elapsed for all the required checks above. The main reason of this is that it just doesn’t take long to do anything with small lists. Below is the exact same algorithm from above, but this time with much larger numbers.

This time the process takes ages! The reason for this is there are ~1 billion iterations occurring which even on a fast machine will take quite a few seconds to complete. In order to make an efficient algorithm to find the GCD we are going to have to think of something new.

Some efficient filtering of values we know are not possible should speed things up. This such as:

1. We can cut out half the checks by removing any values between the lowest number and half the lowest number.
2. Filter out any value that is larger than the difference between the lower and higher numbers.

For the initial example above that would mean instead of 999999999 checks there only needs to be 234567891 checks done which is four times fewer possible iterations.

This is a good saving, but there is an even better option.

Efficient Algorithm

An interesting fact about the Greatest Common Divisor is that while the divisor must equally divide into the given numbers, it must also equally divide into the remainder between the two numbers when the larger is divided by the smaller. This can be done again with the two new smallest numbers gives another smaller value, and repeated until the largest divisor is found.

Lets have a look at an example. Say we are using the two numbers 20 and 8. Using the knowledge that it must divide into the difference we know that our divisor must also go into 4 calculated by 20 % 8.

Taking the remainder between the two lower numbers we can then find that 8 % 4 = 0. Having 0 tells us we have already found the answer which is 4.

This scales really well even for massive numbers. Lets try a larger example.

Numbers are 1234567890 and 999999999.

> 1234567890 % 999999999 = 234567891
> 999999999 % 234567891 = 61728435
> 234567891 % 61728435 = 49382586
> 61728435 % 49382586 = 12345849
> 49382586 % 12345849 = 12345039
> 12345849 % 12345039 = 810
> 12345039 % 810 = 639
> 810 % 639 = 171
> 639 % 171 = 126
> 171 % 126 = 45
> 126 % 45 = 36
> 45 % 36 = 9
> 36 % 9 = 0

So the result for the GCD is 9 which was found after just 13 attempts. Try it out now with different values below to see how many iterations you can make!

NOTE: You are limited by the default Javascript max int value of 9007199254740991.

Conclusion

This efficient algorithm is a great reminder that if there is an interesting numeric problem you are looking at, there may be clever little tricks which hugely reduce that amount of work required. The naive approach is often not a good one either!

What to read more? Check out more posts below!