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.

Advertisements

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 [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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: