Notes Cryptography Mathematical Foundations of Cryptography Greatest Common Divisor

Greatest Common Divisor

17 Dec 2021

§ Motivation

One of the simplest Diophantine equations is of the form $ax + by = c$ . The extended Euclidean algorithm can solve for the greatest common divisor (GCD) between two numbers. The algorithm happens to also solve the Diophantine equation of the form $ax + by = \gcd(x, y)$ , where the coefficients $a$ and $b$ are the Bézout coefficients.

When working in a modular group, Bézout coefficients are useful in a computing the modular inverse of a number, i.e. given $a$ find $b$ such that $ab \equiv_n 1$ .

§ Greatest Common Divisor

Greatest Common Divisor

The greatest common divisor (GCD) is the greatest divisor shared between two numbers.

We often write $(a, b)$ to denote the GCD between $a$ and $b$ , rather than writing $\gcd(a, b)$ .

Properties of the GCD:

$(a, b) = (b, a)$ .
$(0, b) = b$ , zero is divisible by any number.
$(n\cdot a, n\cdot b) = n\cdot (a, b)$ .
$(2a, b) = (a, b)$ if $b$ is odd.
$(a, b) = (\vert a - b\vert, \min(a, b))$ if $u, v$ odd.

These properties are extremely useful in an implementation called "binary GCD". For example, in a C++ fixed-precision integer setting using GCC, we can use __builtin_ctz() to compute case (3) extremely quickly in the case that $n = 2^k$ using bit operations.

§ Euclidean Algorithm

If $(b, c) = g$ , then there exists integers $x_0, y_0$ satisfying the linear Diophantine equation:

bx_0 + cy_0 = (b, c).

Let $A = \{bx + cy, x, y \in \mathbb{Z}\}$ . Choose $x_0, y_0$ such that $l = bx_0 + cy_0$ is the least positive integer in $A$ . Now we want to show that $l = g$ .

Seeking a contradiction, assume $l \nmid b$ . Then the division algorithm gives that $b = lq + r$ for some integers $q, r$ where $0 \lt r \lt l$ .

Then, $r = b - lq = b - q(bx_0 + cy_0) = b(1 - qx_0) + c(-qy_0)$ . This results in $r \in A$ and $0 \lt r \lt l,$ contradiction. The same argument applied on $c$ shows that $l \vert c$ .
Let $g = (b, c)$ , then there exists integers $B, C$ such that $gB = b$ and $gC = c$ . So $l = bx_0 + cy_0 = g(Bx_0 + Cy_0)$ , so $g \vert l$ . Then $g \leq l$ , $l \vert b$ and $l \vert c$ . Therefore, $l$ is the greatest common divisor.

Euclidean Algorithm

Given integers $b, c$ not both equal to zero, the Euclidean algorithm is defined as

\begin{array}{l c l} b = cq_1 + r_1 & \quad & r_1 \in (0\dots c)\\ c = r_1q_2 + r_2 & & r_2 \in (0\dots r_1)\\ r_1 = r_2q_3 + r_3 & & r_3 \in (0\dots r_1)\\ & \vdots &\\ r_{j - 2} = r_{j-1}q_j + r_j &&r_j \in (0\dots r_{j-1})\\ r_{j - 1} = r_jq_{j + 1} & & \text{stop when } r_{j + 1} = 0. \end{array}

Then, the value $r_j = (b, c)$ .

§ Bézout Coefficients

The extended Euclidean algorithm can be used to find Bézout coefficients, i.e. in a given $a, b$ we can find coefficients $s, t$ for the linear Diophantine equation satisfying

s\cdot a + t\cdot b = (a, b).

Extended Euclidean Algorithm

Following the same steps as in the regular Euclidean algorithm, we can find a solution to $bx_0 + cy_0=(b,c)$ by rewriting each $r_i$ in terms of $b$ and $c$ .

\begin{align*} r_1 &= b - cq_1\\ r_2 &= c - r_1q_2\\ &= c - (b - cq_1)q_2\\ &\mkern.5em\vdots\\ r_j &= c\underbrace{(q_1\cdot q_2\cdot \dots)}_{y_0} + b\underbrace{(q_2 \cdot \dots)}_{x_0} \end{align*}

The values $x_0$ and $y_0$ are our Bézout coefficients.

§ Modular Inverse

Modular Inverse

Given $a \in \mathbb{Z}_n$ and $(a, n) = 1$ , we say that $b$ is the modular inverse of $a$ mod $n$ iff

a\cdot b \equiv_n 1.

We also write $b = a^{-1}$ . Keep in mind that we are in $\mathbb{Z}_n$ , therefore $a^{-1}$ must also be an integer.

If we want to find the modular inverse of $a$ modulo $n$ , we can use the extended Euclidean algorithm on $(a, n)$ . Then, the Bézout coefficient corresponding to $a$ is congruent to the modular inverse of $a$ .