Primitive Roots

June 7, 2019

In modular arithmetic, a number g is a primitive root of n if, for every a coprime to n, there exists some k such that gka (mod n). The concept of a primitive root was developed by Gauss and pops up from time to time in work on cryptography and number theory.

There is no formula for computing a primitive root, but they are common enough that it is easy to just randomly search for them; more commonly, people just start at 2 and work their way up. Once a primitive root has been found, the remaining primitive roots of n can be found by exponentiating mod n.

Your task is to write a program that computes the primitive roots of prime n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

One Response to “Primitive Roots”

1. Paul said

In Python. The function factors can be e.g.: factors by trial division.

def totient(n, factors=factors):
result = n
for prime in set(factors(n)):
result -= result // prime
return result

def prim_roots(n):
""" find all primitive roots for any positive n
find one root, then generate the other by exponentiation
root g is found, if g is coprime to n and g^(phi/pi) != 1
for all prime factors pi in totient(n)
"""
if n == 1:  # according to Wikipedia
return 
phi = totient(n)
prs = set(factors(phi))
for g in range(1, n):
if gcd(g, n) != 1:  # g should be coprime with n
continue
if all(pow(g, phi // pi, n) != 1 for pi in prs):
return sorted(pow(g, k, n) for k in range(1, n) if gcd(k, phi) == 1)
return []