A friend of mine is taking a cryptography course this semester. One of his current homework problems involves creating 
, 
, and 
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 
, an exponent , and a modulus 
and returns 
. 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 is odd, you recursively calculate 
and return 
. When is even, you recursively calculate 
and return 
.
(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 and some number 
which is relatively prime to (shares no factors except for one with) , then there exists some number such that 
. And, in fact, all such numbers for a given differ by a multiple of , so there is a unique such 
.
Another way of saying and are relatively prime is to say that their greatest common divisor 
is one. Besides being the biggest number that divides into both and , the is also the smallest positive number expressible as 
for integers 
and 
. If you keep track of the steps you use when calculating the greatest common divisor (which in this case is 
) while using the Euclidean algorithm you can (with enough care) backtrack through the steps and determine and for your given and .
For example, suppose you had 
and 
. You want to know what you’d need for 
.
The steps in the Euclidean algorithm show:
Working backwards, you can express as a combination of 
. Then, you can express 
as a combination of 
and so on:
Wheee… in my example chosen to be easy to backtrack, the answer comes out to be 
which is equal to 
modulo 
. So, 
. I picked a lucky number that is its own inverse modulo . It’s not usually like that. For example, 
.
So, anyhow, here’s a function that takes and and returns two values and so that 
.
(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 and are relatively prime with 
, the first value returned is ‘s inverse modulo .
Recursion, ew.
Here’s the one i’m using:
(defun modular-exp (base exponent modulus)
(loop with result = 1
while (plusp exponent)
if (oddp exponent)
do (setf result (mod (* result base) modulus))
do (setf exponent (truncate exponent 2)
base (mod (* base base) modulus))
finally (return result)))
Thanks for the interesting read. I’ve added these functions to my Emacs environment. I think I found a bug (well, a typo) in expt-mod, the line
(mod (* a a) n)))
should have an m instead of n, shouldn’t it?
Indeed. I had been using different variables than I wanted to use in explaining the code. I didn’t get them all switched. Will fix….