|
Modular Arithmetic and RSA Encryption Stuart Reges, Principal Lecturer |
|
 CSE Home |
About Us |
Search |
Contact Info |
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.
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.