The Modular Inverse
  |   Source

The Modular Inverse

This is the third post in my short series on the RSA algorithm. We met most of the cast of characters used in the algorithm in the last post. Prime numbers, Euclid's algorithm, Bézout's identity, and of course, one of Euler's identities come together to form the foundation of our work. The last detail is the modular inverse. Conceptually, the idea is straightforward, but I feel many articles on RSA don't give it the attention it deserves.

Identities

Many operations paired with sets have an element known as the identity element. This should be a familiar idea even if you haven't seen the formal definition.

  • 0 is the identity of the set $\mathbb{R}$ and the operation of addition. 42 + 0 = 42
  • 1 is the identity of the set $\mathbb{R}$ and the operation of multiplication. 42 * 1 = 42
  • [] is the identity of list concatenation. [40, 41, 42] + [] = [40, 41, 42]

Can you think of other examples? What about the identity of a 3x3 matrix?

$$\begin{bmatrix} 42 & 99 & 2\\ 0 & -35 & 12\\ 4 & 2 & 8 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 42 & 99 & 2\\ 0 & -35 & 12\\ 4 & 2 & 8 \end{bmatrix}$$

Inverses

Informally, and inverse simply "undoes" an operation. Specifically, we are interested in an element that gives us back the identity.

  • $42 + -42 = 0$
  • $42 \cdot \frac{1}{42} = 1$

This works for matrices as well, but keep in mind that not all matrices have an inverse!

$$\begin{bmatrix} 42 & 99 & 2\\ 0 & -35 & 12\\ 4 & 2 & 8 \end{bmatrix} \cdot \begin{bmatrix} \frac{38}{967} & \frac{197}{1934} & \frac{-629}{3868}\\ \frac{-6}{967} & \frac{-41}{967} & \frac{63}{967}\\ \frac{-35}{1934} & \frac{-39}{967} & \frac{735}{3868} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

Put the modular in the inverse

Consider a multiplication table for $\pmod 9$ (excluding 0).

$$\begin{array}{c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 2 & 2 & 4 & 6 & 8 & 1 & 3 & 5 & 7 \\ \hline 3 & 3 & 6 & 0 & 3 & 6 & 0 & 3 & 6 \\ \hline 4 & 4 & 8 & 3 & 7 & 2 & 6 & 1 & 5 \\ \hline 5 & 5 & 1 & 6 & 2 & 7 & 3 & 8 & 4 \\ \hline 6 & 6 & 3 & 0 & 6 & 3 & 0 & 6 & 3 \\ \hline 7 & 7 & 5 & 3 & 1 & 8 & 6 & 4 & 2 \\ \hline 8 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array}$$

A quick inspection will reveal that 1 is indeed the identity element for integers and the multiplication operation. Our intuition is preserved! 😅 As I noted earlier, not all matrices have an inverse. Likewise, not all integers have a modular inverse. Inspect the table closely; can you figure out which numbers do not have an inverse and why?

The integers < 9 that are coprime with 9 and their modular inverse:

  • $8 * 8 \pmod{9} = 1$, 8 is the modular inverse of of 8 in $\pmod{9}$
  • $7 * 4 \pmod{9} = 1$, 4 is the modular inverse of of 7 in $\pmod{9}$
  • $5 * 2 \pmod{9} = 1$, 2 is the modular inverse of of 5 in $\pmod{9}$
  • $4 * 7 \pmod{9} = 1$, 7 is the modular inverse of of 4 in $\pmod{9}$
  • $2 * 5 \pmod{9} = 1$, 5 is the modular inverse of of 2 in $\pmod{9}$
  • $1 * 1 \pmod{9} = 1$, 1 is the modular inverse of of 1 in $\pmod{9}$
Seeking intuition

Given two integers $A$ and $B$, $A$ has a modular inverse in $\pmod{B}$ if and only if A is coprime with B.

Here is how I think about it. Consider $4 \pmod{9}$. You can start at any number and count by multiples of 4. In $\pmod{9}$, you are guaranteed to hit 1 at some point!

  • Start with 30
  • $30 \pmod{9} = 3$
  • count by 4's
  • $34 \pmod{9} = 7$
  • $38 \pmod{9} = 2$
  • $42 \pmod{9} = 6$
  • $46 \pmod{9} = 1$

Can you think of a way to determine the number of steps needed? I covered that in the last post, and it involves Euclid's algorithm and Bézout's identity.

Revisiting Bézout and Euclid

Bézout's identity states:

  • If $a$ and $b$ are positive integers, then there exist integers $k$ and $l$ such that $\gcd(a,b)=ak+bl$

If $a$ and $b$ are chosen so that their $\gcd = 1$, then we want to find some integers $k$ and $l$ where $1=ak+bl$. This is done using Euclid's algorithm as described in the previous post.

Conclusion

I hope this brief discussion clears some of the ideas around the modular inverse. What we are trying to accomplish is given some value, scale it up in a modular space, then be able to get back to where we started. Kind of sounds like an encryption scheme, doesn't it? 😁 In my next post in this series, I will finally describe the actual RSA algorithm and how all of these pieces fit together.