
Modular Arithmetic and RSA
Encryption Stuart Reges, Principal Lecturer


.
This page collects resources for a talk given in conjunction with the 2011
Computer
Science & Information Symposium on July 12th at Columbia University. The
symposium was organized by the Computer
Science Teachers Association.
 slides from talk (ppt, pdf)
 handout from talk (doc, pdf)
 starter Python file (we uncommented various
lines as we replaced the "?" with actual values)
 final Python file
 Java has a BigInteger
class that allows you to store arbitrarily large integers. It isn't as
easy to use as Python's interface, but it includes some things Python
doesn't like an isProbablePrime
method and a modPow
method that is like ours. The program Prime.java picks random 200digit primes.
 How do you test whether something is probably a prime? Given a number n
that might be prime, you can pick a random value a and see whether
modpow(a, n1, n) is 1. Fermat's
Little Theorem says it should be. If it is, then n is probably
prime. You want more evidence? Pick another a. There's a little more
to it, because there are some integers known as Carmichael
numbers that satisfy Fermat's Little Theorem even though they aren't
prime, but that's the basic idea. Read about MillerRabin
primality testing if you want to understand the stateoftheart
approach.
 The National Security Agency hires more mathematicians than any other
organization because so much of modern cryptography is built on
mathematics. If you read about job
opportunities at the NSA, you'll see the computer science is high on
their list of "top jobs." They also have scholarships.
They have a funny site called CryptoKids.
 Wikipedia has lots of resources on RSA encryption and the
RSA
factoring challenge.
 RSA would be broken if someone were to invent a quantum computer
because then they could use Shor's Algorithm to
find the prime factors of the modulus. If anyone has a
quantum computer, it's the NSA (and they wouldn't tell us).
 For further exploration, read the chapter on cryptography in the book
Blown to Bits which can be downloaded for free (entire book
or just chapter 5)
Below are notes on the steps we followed to develop the modpow function.
We discussed the idea of writing a modpow function that would compute:
a ^ n mod m
We started with this version of modpow:
def modpow(a, n, m):
result = 1
while n > 0:
result = result * a
n = n  1
return result % m
We saw that we could speed this up by applying mod to intermediate results:
def modpow(a, n, m):
result = 1
while n > 0:
result = (result * a) % m
n = n  1
return result % m
That's an important speedup, but it still is an O(n) operation because it does
n multiplications and mods inside the loop. How do we do better?
We noticed that we could do better for even exponents. Using a loop invariant
(to help us keep track of what relationship among variables we need to
maintain), we changed our code to:
def modpow(a, n, m):
result = 1
while n > 0:
if n % 2 == 0:
n = n / 2
a = a * a
else:
result = (result * a) % m
n = n  1
return result % m
Unfortunately, this turned out to be slow. That's because we reintroduced our
problem of not applying mod to intermediate results when we square a. We also
noticed that it was better to mod a by m initially and then we didn't need to
mod result by m at the end. So we ended up with this:
def modpow(a, n, m):
result = 1
a = a % m
while n > 0:
if n % 2 == 0:
n = n / 2
a = a * a % m
else:
result = (result * a) % m
n = n  1
return result
This version is well behaved even for very large values (hundreds of digits)
for any of a, n or m.
Stuart Reges
Last modified: Tue Jul 12 16:09:46 PDT 2011