  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 200-digit 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, n-1, 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 Miller-Rabin primality testing if you want to understand the state-of-the-art 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