Cryptography requires key ideas from mathematics to be able to generate cryptosystems. The most important branch of mathematics is known as number theory. Number theory is the study of the set of positive whole numbers, often called the natural numbers.
There are a couple of mathematical definitions we need to be aware of regarding division to help us with cryptography:
Definition 1:If a and b are integers, and a = qb for some integer q, then we say that b divides a, b is a factor of a or a is a factor of b.
Definition 2:If d divides a and c divides b, we say that d is a common divisor of a and b. For example, 1 is a common divisor of any pair of integers a and b. If a and b are not both 0, then no common divisor is greater than max(|a|, |b|). This value is the greatest common divisor (GCD) of a and b. It is a unique integer satisfying:
1. d divides a and d divides b (d is a common divisor)
2. if c divides a and c divides b, then c ≤ d (no common divisor exceeds d)
You may have noticed that we have excluded the case where a and b both equal 0. This is because every integer divides 0 so it is therefore a common divisor of a and b, leaving no GCD. We denote the gcd of a and b as gcd(a, b).
The GCD is also known as the highest common divisor or the highest common factor and is often calculated to simplify a fraction of 2 numbers to it's lowest terms. For example, 9/16 can be simplified to 3/4 where 3 is the highest common factor.
To calculate the GCD, we use the Euclidean Algorithm. It is named after the ancient Greek mathematician Euclid and is a very efficient way of calculating the GCD.
Before we move onto learning how to calculate the GCD using the Euclidean Algorithm, there is one last lemma we must note:
If a = qb + r then gcd(a, b) = gcd(b, r).
To prove this we can see that any common divisor of b and r also divides qb + r = a since a is the sum of factors of b and r. Similarly, since r = a - qb, it follows that any common divisor of a and b also divides r. Thus the two pairs a, b and b, r have the same common divisors, so they have the same greatest common divisor.
Written by JaneW