Mostly because of their importance in some types of asymmetric cryptography (Diffie-Hellman, RSA) I have a fascination with prime numbers. I enjoy occasionally checking on the latest discovery of ever larger prime numbers. As I write the largest known prime has more than 17, 425, 170 digits in it. That’s a big-ass number! Many years ago I wanted to get a blanket made that had the largest prime printed on it. Geek stuff, I know.
One of the important components of a Diffie-Hellman key exchange is the use of a primitive root for a given prime number. I know what a primitive root is but if I try to explain it here I’ll just make mathematicians angry. I’ll direct you instead to Wikipedia’s discussion of primitive roots and ask that you read, at the very least, the first sentence of the article. If you want to watch some really awesome videos on modern cryptography that will briefly discuss what a primitive root is (and why it’s important) check out this video discussing the discrete logarithm problem on the Khan Academy website. You should watch the whole series on the Khan Academy website; it is excellent (do a Google search for “Journey Into Cryptography“).
In class I use a python script to illustrate the Diffie-Hellman key exchange but I always used really small primes (like 17 or 47). They work just fine but I wanted to be able to use larger numbers to further illustrate the concepts and math at work. To do that I needed to be able to figure out the primitive roots of larger prime numbers. Googling for primitive roots of primes didn’t give me a lot so I wanted to see if I could get python to help me out. The code below works (to the very best of my knowledge). I have used it for many different primes and the primitive roots generated always work in my Diffie-Hellman math examples (which I will post in an upcoming Edition)
Here’s the Code:
#!/usr/bin/env python
# This script will generate all of the primitive roots
# for a given prime number.
prime = int(raw_input("Enter a prime number: "))
num_to_check = 0
p_minus_1_range = range(1,prime)
print "If you entered a large number (4+ digits) this could take a long time."
print ""
print "Working..."
primitive_roots = []
for each in range(1, prime):
num_to_check += 1
candidate_prim_roots = []
for i in range(1, prime):
modulus = (num_to_check ** i) % prime
candidate_prim_roots.append(modulus)
cleanedup_candidate_prim_roots = set(candidate_prim_roots)
if len(cleanedup_candidate_prim_roots) == len(range(1,prime)):
primitive_roots.append(num_to_check)
print "Primitive roots of %d are:" % prime
print "-----------------------------------"
print primitive_roots,Note: Depending on the size of the prime you enter it could take a while to sort things out. Even though the script is pretty short there is a whole bunch of number crunching going on. In my tests on my late 2013 Macbook Pro (Intel 2.6GHz Core i7 with 16GB RAM) it took a little over 4 minutes to calculate all of the primitive roots of the prime 1907. All of the primitive roots for the prime 941 were generated in 28 seconds. Generating all of the primitive roots for the prime 5051 took an impressive 113 minutes. It’s also worth noting that the script uses a pretty big chunk of RAM (about 6GB in my generation of the primitive roots of 5051). So if you want to generate primitive roots of big primes, either be patient or get a better computer than the one I am using.
Linus and OSX users: If you want to know how long the script takes to complete, try running it with the time command (i.e. time ./primitive_root_finder.py)
Cheers,
Colin Weaver
If you liked this post, please consider sharing it. Thanks!
