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 gk ≡ a (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

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “Primitive Roots”

  1. Paul said
    June 9, 2019 at 9:42 AM

    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 [0]
    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 []

Leave a comment