Euclid's algorithm for Greatest Common Divisors

Well, isn't that title exciting? Today I bring you more math. This particular math is important for some types of cryptography, so instead of explaining it all in a post on the little cipher I implemented, I figured I'd write up a separate post.

The fundamental theory of arithmetic states that all positive integers have a unique prime factorization. This means that any number can be reduced into a product of at least one prime. Prime numbers are numbers where the only factors are 1 and itself. Numbers with more than one prime factor are composite numbers. That is, they are a product of some number of integers > 1. (Side note: 1 is neither a prime nor composite number, and is therefore often called the "unit.")

The Greatest Common Divisor (gcd) of two or more numbers is the largest number that evenly divides all of them. For example, the gcd(10, 20) is 10, because 10 evenly divides 10 and 10 also evenly divides 20. We use the symbol | to denote "divides". We can then write,
gcd(12,20) = 4 because 4 | 12 and 4 | 20
To denote "does not divide" we use ∤ (Unicode 2224, in case you're wondering)
gcd(13,20) ≠ 4 because while 4 | 20, 4 ∤ 13
You can easily see that any prime number (p) will have a gcd of 1 with any other number less than p; that is a prime number by definition will not have a common divisor with any number less than itself. Any two numbers that have a gcd of 1 are called relatively prime to each other.

Using FTA to find GCD

Theoretically we can calculate the GCD using the fundamental theory of arithmetic. If we factor each number down to its base prime components, we can then take the smallest exponent of each prime factor and use those to make a new number. That new value is the GCD. Think of it like this: if we take the lowest exponent of each factor to make our gcd, the gcd will only contain factors it shares with both "parents".
The simplest way to get the prime factorization is to successively divide the number (well, its remainder) evenly by each prime until we reach 1. For example, to factor 12 and 20 we would do:
12 / 2 = 6
6 / 2 = 3
We now have our first prime factor of 12, that is 22. It took two rounds of division by 2 to get to a number not divisible by 2. We continue with the next prime, which is 3:
3 / 3 = 1
We have reached one and are now done.
The prime factorization of 12 is 22 * 3
We can do the same to find the prime factorization of 20:
20/2 = 10
10/2 = 5
(3 ∤ 5, so move on to the next prime)
5 / 5 = 1

Prime factorization of 20 is 22 * 5

To get the GCD, you take the lowest exponent of each prime that shows up in that list and find the product. Continuing with our example, it would be:
20 = 22 * 5
12 = 22 * 3

or, writing everything explicitly,
20 = 22 * 30 * 51
12 = 22 * 31 * 50

Takeing the lowest exponent found of each prime gives,
gcd(20,12) = 22 * 30 * 50
= 4 * 1 * 1
= 4

This works alright for small values, but becomes quite tedious and computationally heavy for large values (it's still good to be aware of its existence). Finding the prime factorization of large numbers is almost NP-complete (not confirmed NP-complete, but known NP-hard), effectively meaning that there probably isn't an efficient algorithm to solve it. There are some algorithms that are better than the simple one I used above, but they still aren't great. For example, the most recent achievement in this field was that a distributed cluster took six months (and 2 years to do the prep work) to factor a 232 digit number into its two component primes. If an efficient algorithm could ever be found it would mean that several methods of cryptography could easily be broken. Exciting stuff.

Euclidean Algorithm

Alright, so there is a better way to find GCDs that completely passes over prime factorizations. This is the Euclidean Algorithm. It relies on the division algorithm, which states that any number can be expressed as a product of two numbers plus a remainder.
a = bq + r
a is our number, the dividand
b is our divisor
q is our quotient
r is the remainder
For example, the number 23 can be expressed in terms of 5:
23 = 5 * 4 + 3
This may look familiar if you read my earlier post about modular arithmetic here. The definition of congruence is simply the above equation rearranged.

The algorithm to find gcd(a, b) goes like this:
- Express a in terms of b using the division algorithm
- Shift b to the dividend place, r to the divisor place, and express b in terms of r.
- Repeat the shift-then-express until we reach a remainder of 0. The second-last remainder will be the GCD.
In the above example, the GCD is 2, which is the second-last remainder.

Side note: The order of the numbers doesn't matter, as the first step of the reverse order will simply have a quotient of zero and a large remainder:

14 = 82 * 0 + 14
82 = 14 * 5 + 12
14 = 12 + 1 + 2
12 = 2 * 3 + 0

You may notice that to get each quotient is an integer divide of (dividend \ divisor) and to get each remainder is a mod function (dividend mod divisor).

This is quite simple to implement in code. I threw this together in VBA because VBA is close to pseudocode in that you often have to be very explicit... (and I can mash together a GUI very quickly.)

'Implementation of Eucledian algorithm for calculating the
'Greatest Common Divisor between two integers
'Returns the GCD as an Integer.

Function gcd(a As Integer, b As Integer) As Integer
    Dim dividend As Integer
    Dim divisor As Integer
    Dim remainder As Integer
    'The expression a = b * q + r will become
    'dividand = divisor * quotient + remainder
    'remainder will be calculated each loop
    'We don't need to track quotients so we don't calculate them
    dividend = a
    divisor = b
    remainder = dividend Mod divisor
    Do While remainder > 0
        'Shift over b and r to replace a and b
        dividend = divisor
        divisor = remainder
        'calculate new r
        remainder = dividend Mod divisor

    gcd = divisor 'previous round's remainder
End Function


Something that's sort of interesting here is when you try to find the gcd of two Fibonacci numbers:


55 = 34*1 + 21
34 = 21 * 1 + 13
21 = 13 * 1 + 8
13 = 8 * 1 + 5
8 = 5 * 1 + 3
5 = 3 * 1 + 2
3 = 2 * 1 + 1
2 = 1 * 2 + 0
Does that sequence of remainders look familiar? It's the Fibonacci sequence (missing one 1)!

0 things about

Euclid's algorithm for Greatest Common Divisors

Post a Comment

Copyright 2012 Phile not Found. See About
Powered by Blogger

"Whenever you find that you are on the side of the majority, it is time to pause and reflect."