Wrapped In Python – Edition 4 – Primitive Root Finder

Using Python to Find Primitive Roots of a Prime Number

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!

About the Author

Colin Weaver

Colin Weaver is co-owner and lead instructor at ITdojo, Inc., a network security and information assurance training center and consulting firm located in Virginia Beach, VA. His passion for technology, networks, and security has led him to become enthralled with the idea of IPv6 and its implementation. In this blog he will share with you glimpses of what he has learned and a hint at what you’ll learn in his classes.