## Two snippets that I rewrite every three or four months…April 23rd, 2013 Patrick Stein

A friend of mine is taking a cryptography course this semester. One of his current homework problems involves creating $n$, $e$, and $d$ values for RSA Encryption. Always one to play the home game when math is involved, I found myself rewriting two snippets of code that I always end up writing any time I do any number-theory related coding.

One of them is simple EXPONENT-MODULO that takes a base $b$, an exponent $e$, and a modulus $m$ and returns $b^e \pmod m$. There are more efficient ways to do this, but this one is much faster than the naïve method and quite easy to rewrite every time that I need it. The idea is that when $e$ is odd, you recursively calculate $b^{e-1} \pmod m$ and return $b \cdot b^{e-1} \pmod m$. When $e$ is even, you recursively calculate $a = b^{e/2} \pmod m$ and return $a^2 \pmod m$.

(defun expt-mod (b e m)
(cond
((zerop e) 1)
((evenp e) (let ((a (expt-mod b (/ e 2) m)))
(mod (* a a) m)))
(t (mod (* b (expt-mod b (1- e) m)) m))))

The other snippet of code is a good deal trickier. Every time I need it, I spend way more time than I want to futzing with examples, getting lost in subscripts, etc. So, while I could rewrite the above in a moment, what’s below, I hope I have the search-fu to find this post next time I need it.

If you have a number $n$ and some number $a$ which is relatively prime to (shares no factors except for one with) $n$, then there exists some number $b$ such that $a \cdot b \equiv 1 \pmod n$. And, in fact, all such numbers $b$ for a given $a$ differ by a multiple of $n$, so there is a unique such $b \in [1,n)$.

Another way of saying $a$ and $n$ are relatively prime is to say that their greatest common divisor $\gcd(a,n)$ is one. Besides being the biggest number that divides into both $n$ and $a$, the $\gcd(a,n)$ is also the smallest positive number expressible as $x \cdot a + y \cdot n$ for integers $x$ and $y$. If you keep track of the steps you use when calculating the greatest common divisor (which in this case is $1$) while using the Euclidean algorithm you can (with enough care) backtrack through the steps and determine $x$ and $y$ for your given $a$ and $n$.

For example, suppose you had $n = 40$ and $a = 31$. You want to know what $b$ you’d need for $31b \equiv 1 \pmod{40}$.
The steps in the Euclidean algorithm show:

$\begin{array}{rcl}40 & = & 31 \cdot 1 + 9 \\31 & = & 9 \cdot 3 + 4 \\9 & = & 4 \cdot 2 + 1\end{array}$

Working backwards, you can express $1$ as a combination of $x_0 \cdot 4 + y_0 \cdot 9$. Then, you can express $4$ as a combination of $x_1 \cdot 9 + y_1 \cdot 31$ and so on:

$\begin{array}{rcl}1 & = & (-2)\cdot4 + 9\cdot{1} \\ & = & (-2)\cdot\left((-3)\cdot9 + 31\right) + 9\cdot{1} \\ & = & (-2)\cdot31 + 7\cdot9 \\ & = & (-2)\cdot31 + 7\cdot(40 - 31\cdot1) \\ & = & (-9)\cdot31 + 7\cdot(40) \equiv 1 \pmod{40}\end{array}$

Wheee… in my example chosen to be easy to backtrack, the answer comes out to be $-9$ which is equal to $31$ modulo $40$. So, $31^2 \equiv 1 \pmod{40}$. I picked a lucky number that is its own inverse modulo $40$. It’s not usually like that. For example, $3 \cdot 27 \equiv 7 \cdot 23 \equiv 1 \pmod{40}$.

So, anyhow, here’s a function that takes $a$ and $n$ and returns two values $x$ and $y$ so that $x\cdot{}a + y\cdot{}n \equiv \gcd(a,n) \pmod n$.

(defun gcd-as-linear-combination (a n)
(multiple-value-bind (q r) (truncate n a)
(if (zerop r)
(values 1 0)
(multiple-value-bind (x y) (gcd-as-linear-combination r a)
(values (- y (* q x)) x)))))

Assuming that $a$ and $n$ are relatively prime with $a < n$, the first value returned is $a$‘s inverse modulo $n$.