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

- We can cut out half the checks by removing any values between the lowest number and half the lowest number.
- 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!