A note about evaluating expressions "mod $n$"

We went over the facts that \[ (a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n \] and \[ (a b) \bmod n = ((a \bmod n) (b \bmod n)) \bmod n. \] This means that when evaluating arithmetical expressions "mod n" we are free to reduce mod n at the very end only, or after every operation, or to sprinkle mod n's in wherever we want.

The Euclidean Algorithm

We saw last class that the existence of a multiplicative inverse "mod n" is tied up with gcd's. We went over the Euclidean GCD Algorithm (see Unit notes). This is very important for all sorts of reasons, but in the "multiplicative inverse" discussion, it was important because it allowed us to determine when a number has an inverse.

Algorithm: GCD(x,y)
Input : integers x,y ≥ 0
Output: g such that g is the gcd of x and y
------------------------
  (a,b)   = (x,y)

  while b != 0 do
    (q,r) = divide(a,b) ← i.e. a = q*b + r, 0 ≤ 0 < b
    (a,b) = (b,r)

  return a
}

We proved this algorithm to be correct using the loop invariant $\text{gcd}(x,y) = \text{gcd}(a,b)$.

The Extended Euclidean Algorithm

We can augment the Euclidean GCD algorithm to compute not only the GCD, but two extra values called the "cofactors". Below is the resulting algorithm, the Extended GCD algorithm. The augmentations are colored green.

Algorithm: XGCD(x,y)
Input : integers x,y ≥ 0
Output: g,s,t such that g is the gcd of x and y, and g = s*a + t*b
------------------------
  (a,b)   = (x,y)
  (sa,ta) = (1,0)
  (sb,tb) = (0,1)

  while b != 0 do
    (q,r) = divide(a,b) ← i.e. a = q*b + r, 0 ≤ 0 < b
    (sr,tr) = (sa - q*sb,ta - q*tb)
    (sa,ta) = (sb,tb)
    (sb,tb) = (sr,tr)
    (a,b) = (b,r)

  return (a, sa, ta);
}

Great, huh? But do you actually have any reason to believe it works? What would it take to convince you that it works? This is actually quite a simple algorithm in the grand scheme of things, but already it's hard to be confident it is correct. Let me try to convince you! Here's a loop invariant for you: \[ a = s_a x + t_a y \text{ and } b = s_b x + t_b y \] So let's do this:

1. Initialization: As we encounter the loop for the first time, we have \[ a = x = 1\cdot x + 0\cdot y = s_a x + t_a y \text{ ... check!} \text{ and we have } b = y = 0\cdot x + 1\cdot y = s_b x + t_b y \text{ ... check!} \] So the invariant holds at the beginning
2. Matainance: Assuming the invariant holds, we have \[ a = qb + r \Rightarrow r = a - qb = (s_a x + t_a y) - q(s_b x + t_b y) = (s_a - q s_b) x + (t_a - q t_b) y = s_r x + t_r y \] Then we set $(s_a,t_a) = (s_b,t_b)$ so that after the assignment $a = b$ we have the first part of the invariant. Then we set $(s_b,t_b) = (s_r,t_r)$ so that after the assignment $b = r$ we have the second part of the invariant.
3. Termination: When the loop exits, $a$ is the gcd of $x$ and $y$, as required. The loop invariant tells us that $a = s_a x + t_a y$, so returning $(g,s,t) = (a,s_a,t_a)$ meets the algorithm's specification.

Some important notes: The loop invariant is not the loop continuation condition. It is something new that is not in the code, but tells us something extra about the code. Second, the loop invariant references variables from the program, referring to their value at a point in time. We don't write something like "$a_i$", intending to indicate the value of $a$ "at the $i$th iteration". That's not how it works. The invariant is true each and every time we get to the point where we are about to check the loop continuation condition. Finally, the invariant is strong enough that, we can easily use it to prove the program correct.

When a multiplicative inverse "mod n" exists: The whole story!

We showed last class that when $\gcd(n,a) \neq 1$, $a$ has no multiplicative inverse in $Z_n$. However, is it true that when $\gcd(n,a) \neq 1$ in means that $a$ does have a multiplicative inverse in $Z_n$? Yes! Here's the cool part: If the gcd(n,a) = 1, then when can call XGCD(n,a) we get (1,s,t) such that $1 = s n + t a$. This means that $t a = -s n + 1$, which means that $t a = 1 \bmod{n}$ Therefore, $t$ is the multiplicative inverse of $a$! NOTE: if $t$ is a negative number (e.g. -12) you have to interpret that as the additive inverse mod n. So if n = 17 and t = -12, -t = 5 would be the multiplicative inverse.

Why do we care about the multiplicative inverse "mod n"?

We went over a simple example of a (not secure!) encryption function. If you want to encrypt $n$ bits at a time, you choose as your secret key numbers $a$ and $b$, both in the range $(0,2^n)$, with $a$ odd. We view our $n$-bit message as an element of $Z_{2^n}$. Then ecryption for message chunk $M$ is: \[ e(M) = aM + b \] What about decryption? Well, call the encrypted message $M'$, we know that $M' = aM + b$. We can solve for $M$ in terms of $M'$ if we can find $b$'s additive inverse and $a$'s multiplicative inverse. We get $M = a^{-1}(M' + (-b))$. So the decryption function is: \[ d(M') = a^{-1}(M' + (-b)) \]