# Euclidean Algorithm - Cryptography Tutorial

## Perform Euclidean Algorithm Cryptography > Tools > The Euclidean Algorithm (45 min.) Objectives: 1) Understand  the Euclidean Algorithm to determine the greatest common divisor of 2 integers. 2) Learn how to program the Euclidean Algorithm.

The Euclidean Algorithm

We encountered that some ciphers require the knowledge of the greatest common divisor of two integers, others require the usage of two integers with a 1 as a common divisor. On this page, I will demonstrate to you how the Euclidean Algorithm can be used in both instances. It is named after Euclid since he was the first person to describe this mathematical procedure. It is easy to understand as you will see below and it is the most efficient method to compute the greatest common divisor (in brief "gcd"). Even the gcd of i.e. two 9-digit numbers can be found quickly.

Let's recall some school terminology: When dividing one integer by another (nonzero) integer we get an integer quotient (the "answer") plus a remainder (generally a rational number). For instance,

13/5 = 2 ("the quotient") + 3/5 ("the remainder").

We can rewrite this division in terms of integers as follows:

13 = 2 * 5 + 3.

This expression is obtained from the one above it through multiplication by the divisor 5.

We refer to this way of writing a division of integers as the Division Algorithm for Integers. More formally stated:

If a and b are positive integers, there exist unique non-negative integers q and r so that  a = qb + r , where 0 <= r < b.

where q is called the quotient and r the remainder.

The greatest common divisor of integers a and b, denoted by gcd(a,b), is the largest integer that divides (without remainder) both a and b. So, for example:

 gcd(15, 5) =5, gcd(9,3) =3, gcd(19, 9) =1, gcd(81, 57) =3.

The gcd of two integers can be found by repeated application of the division algorithm, this is known as the Euclidean Algorithm. I.e.: To find the gcd of 81 and 57 by the Euclidean Algorithm, we proceed as follows:

81 = 1 * 57 + 24

57 = 2 * 24 + 9

24 = 2 * 9 + 6

9 = 1 * 6 + 3

6 = 2 * 3 + 0.

We repeatedly divide the divisor by the remainder until the remainder is 0. The gcd is the last non-zero remainder in this algorithm, 3 in our example.

Exercise 1:
Find the greatest common divisor of 26 and 21 using the Euclidean Algorithm by hand.   1

Exercise 2:
Find the greatest common divisor of 81 and 54 using the Euclidean Algorithm by hand.   27

Exercise 3:

Find the greatest common divisor of 81 and 51 using the Euclidean Algorithm by hand.    3

Exercise 4:
Find the greatest common divisor of 3456 and 1720 using the Euclidean Algorithm by hand.   8

Implementation of the Euclidean Algorithm

The Euclidean Algorithm should be performed by a computer. It is very easy to implement and it yields the answer quickly. If you happened to study Computer Sciences in College you are almost guaranteed to encounter this algorithm in one of your first classes. The reason:  Only a few lines of code are needed to implement a very efficient algorithm. Here they are:

 while (r != 0){ r = a % b; a = b; b = r; } a = larger integer,  b = small integer,  r = remainder.

The gcd is found as the value of a when r is 0. (What is the value of b at that time?) I used this code below so that you can compute the gcd of any two integers a and b. Additionally, you can observe the steps involved that lead to the final answer. Thus, enter the two integers a and b followed by hitting the "Compute GCD" button to scrutinize the computation process until the gcd is found.

Enter a= - the larger integer.
Enter b= - the smaller integer (the modulus in some cases).

The GCD can be read off as the remainder in the 2nd to last line:

To observe the efficiency of the algorithm compute i.e. GCD(81543254,57435333). Euclid of Alexandria (325-265 BC)  was the most prominent Mathematician at his time. He summarized his discoveries in "The Elements". Here is an excerpt: 1. There are infinitely many primes. 2. Euclidean Geometry. 3. Euclidean Algorithm.

Related web sources:

Cut-the-knot.com (Play the Euclid game here)

Encarta.com

Glossary

PBS Online

Introduction to Cryptography

Enigma and the Codebreakers

Enigma History

Enigma Emulator

top