SI242: gcd, egcd and a little encryption

Recapping: a hypothesis about inverses mod n

The greatest common divisor of two integers $u$ and $v$, at least one of which is non-zero, is the largest positive number that divides both $u$ and $v$. We use the expression $\text{gcd}(u,v)$ denote the greatest common divisor.

Since $1$ divides everything, the gcd should always be at least 1. Based on last class's activity, folks made the following hypothesis (or something equivalent to it):

Hypothesis $\text{gcd}(x,n) = 1$ if and only if $x$ has a multiplicative inverse in $\mathbb{Z}_n$

Note that "if and only if" means that we have an equivalence. So the hypothesis is $A \Leftrightarrow B$, where $A$ is "$\text{gcd}(x,n) = 1$" and $B$ is "$x$ has a multiplicative inverse in $\mathbb{Z}_n$". So to prove this, we need to prove:

$A \Rightarrow B$
$B \Rightarrow A$

Last class we proved , which states, in slightly different words, that if $\text{gcd}(x,n) \neq 1$ then $x$ does not have a multiplicative inverse in $\mathbb{Z}_n$. So which of the above have we proved? Well what we proved is $\neg A \Rightarrow \neg B$ which is the contrapositive of $B\Rightarrow A$. So what remains to be proved is $A \Rightarrow B$, i.e.:

$\text{gcd}(x,n) = 1$ implies $x$ has a multiplicative inverse in $\mathbb{Z}_n$

We will only sketch that part, as we simply don't have time to do more right now.

gcd

You've seen the euclidean gcd algorithm in IC210 done with loops. Here it is recursively:

Algorithm: GCD(u,v) - [The Euclidean GCD algorithm]
Inputs: integers u and v such that  0 ≤ v ≤ u, and u ≠ 0
Output: g where the gcd of u and v				      
if v = 0
  g = u
else
  q,r = div(u,v)
  g = GCD(v,r)
return g

Example

  u   v   q   r   g	      
--------------------------	      
 51  42   1   9
 42   9   4   6
  9   6   1   3
  6   3   2   0
  3   0           3  ← g=3 gets passed all the
                       way back up. gcd(51,42) = 3

We did not have time in class to prove that this gives the actual gcd of u and v. But here is the full proof.

The Euclidean algorithm is correct, i.e. it meets its input/output specifications.

We need to prove that for integers $u$ and $v$ satisfying $0 \leq v \leq u$ and $u \neq 0$, the value $g$ returned by GCD($u$,$v$) is the gcd of $u$ and $v$. We will prove this by induction on $v$, the second input to GCD.
When $v = 0$, the algorithm returns $g = u$, which divides both $u$ and $v$, and is as big as possible, since anything larger would not divide $u$.
So consider the case $v > 0$. The algorithm calls div($u$,$v$), which returns quotient $q$ and remainder $r$ such that $u = q v + r$.

If $h$ is a common divisor of $v$ and $r$ then $v = h a$ and $r = h b$, and $u = q v + r = q h a + h b = h(qa + b)$, which means that $h|u$. Thus $h$ is a common divisor of $u$ and $v$.
If $h$ is a common divisor of $u$ and $v$, then $u = h c$ and $v = h d$, and since $u = q v + r$, we have $r = u - q v = h c - q h d = h(c - q d)$, which means that $h$ is a common divisor of $v$ and $r$.

Putting the two points above together, we get that

$h$ is a common divisor of $u$ and $v$ if and only if $h$ is a common divisor of $v$ and $r$

and therefore, the set of common divisors of $u$ and $v$ is the same as the set of common divisors of $v$ and $r$ and, in particular, their greatest common divisors are the same. By the inductive hypothesis, we may assume that the value returned by the call to GCD($v$,$r$), which we store in $g$, is the greatest common divisor of $v$ and $r$, and thus $g$ is the greatest common divisor of $u$ and $v$, as required. Therefore, by the principle of induction, we have proved that Euclidean gcd algorithm is correct for all inputs.

egcd

We also discussed that with a little extra bookkeeping we get the "extended gcd algorithm", egcd, that returns three numbers, g, s, ant t, such that

$(g,s,t) = \text{egcd}(u,v)$, where $g$ is the gcd of u and v, and $g = s\cdot u + t\cdot v$.

Algorithm: eGCD(u,v) - [The Extended Euclidean GCD algorithm]
Inputs: integers u and v such that  0 ≤ v ≤ u, and u ≠ 0
Output: g,s,t where the gcd of u and v  and g = s u + t v  
if v = 0
  g,s,t = u,1,0
else
  q,r = div(u,v)
  g,s',t' = eGCD(v,r)
  s = t'
  t = s' - q 
return g




	      

          Why this works         
g = s' v + t' r assume the recursive call works (ind. hypothesis)
u = q v + r by the definition of division
u - q v = r rewriting the line above
g = s' v + t' (u - q v) substituting u - qv for r
g = s' v + t' u - t' q v expanding
g = t' u + (s' - t' q) v
   ---     -----------
    s           t

This actually solves the problem for finding multiplicative inverses, because if the gcd of $x$ and $n$ is 1, then $(1,s,t) = \text{gcd}(x,n)$ where $1 = s\cdot x + t\cdot n$, which we can rewrite as $s\cdot x = -t\cdot n + 1$. So $s\cdot x \bmod n = 1$, which means that $s$ is the multiplicative inverse of $x$. This not only proves the "$A\Rightarrow B$" part of the hypothesis, but also gives us a way to compute multiplicative inverse mod $n$.

Recapping: a hypothesis about inverses mod n

gcd

egcd

Simple encryption with modular arithmetic