Mathematical Cryptography

Section 2.2 Common divisors and the Euclidean algorithm

It turns out that the straightforward idea of numbers possessing divisors in common has important consequences for the construction of secure mathematical encryption schemes.

As a common divisor can be no larger than either of the numbers \(a\) and \(b\text{,}\) there always must be a largest such \(d\text{,}\) called the greatest common divisor. We denote the greatest common divisor of \(a\) and \(b\) with the symbol \(\gcd(a,b)\text{.}\) Finding a gcd is straightforward task in the case that the numbers are small - we can perform a factorization of the numbers, compare factors, and construct the gcd by multiplying all of the factors that the numbers have in common. For example, \(\gcd(128, 36) = 4\) because \(128 = 2^7\) and \(36 = 2^2 3^2\text{,}\) and thus the numbers share \(2^2\) as a common factor. However, at the scale of numbers used in cryptography, this is not an efficient method for finding a gcd.

We need an alternative approach. Fortunately, an easy observation about the division algorithm will provide the foundation for a significantly more efficient method. Let \(a, b \in \Z\text{.}\) By the division algorithm, there are unique numbers \(q, r \in \Z\) with \(0 \leq r \lt b\) so that

Observe that if \(d \mid a\) and \(d \mid b\) then \(d \mid r\text{.}\) (Why?) Observe that if \(e \mid b\) and \(e \mid r\) then \(e \mid a\text{.}\) (Why?) This means that the common divisors of \(a\) and \(b\) are the same as the common divisors of \(b\) and \(r\text{.}\) We conclude that \(\gcd(a,b) = \gcd(b, r)\text{.}\) This reduction of complexity gives us the core step in what is known as the Euclidean algorithm. Finally, observe that since every nonzero integer divides \(0\text{,}\) we have \(\gcd(n, 0) = n\text{.}\)

There is actually more information contained in the calculation above. Let \(a = 2024\) and \(b = 748\text{.}\) Using a series of cascading substitutions, we can show that

In fact, it is always the case that \(\gcd(a,b)\) can be written as an integer linear combination of \(a\) and \(b\text{,}\) a result known as the extended Euclidean algorithm.

1. Use the Euclidean algorithm to find the string of quotients \(q_1, \ldots, q_n\) appearing in the descending equations, where \(n\) is the number of steps required to reach remainder 0.

2. Construct two recursive sequences, \(P\) and \(Q\text{.}\)

   1. Set \(P_0 = 1, P_1 = q_1\) and \(P_{k} = q_k \cdot P_{k-1} + P_{k-2}\) for \(2 \leq k \leq n\text{.}\) The sequence will terminate with \(P_n = a\text{.}\)
   2. Set \(Q_0 = 0, Q_1 = 1\) and \(Q_{k} = q_k \cdot Q_{k-1} + Q_{k-2}\) for \(2 \leq k \leq n\text{.}\) The sequence will terminate with \(Q_n = b\text{.}\)
3. The final terms of the sequence will satisfy the equation
   \begin{equation*} a Q_{n-1} - b P_{n-1} = (-1)^n. \end{equation*}
   Dividing through by \((-1)^n\) will give
   \begin{equation*} a ((-1)^n Q_{n-1}) - b ((-1)^n P_{n-1}) = 1, \end{equation*}
   which gives \(u\) and \(v\text{.}\)

You should notice that the algorithm can actually be used on any pair \(a, b\) by dividing through by the gcd.

You can make a nice visual representation of the algorithm with an array:

The above algorithm is powerful, but requires storing potentially lots of information. There are more efficient approaches, though you may wish to implement the algorithm above.