Primitive Roots

June 7, 2019

Here is our function to calculate primitive roots:

(define (prim-roots p)
  (let ((fs (unique = (factors (- p 1)))))
    (let loop ((a 1) (ps fs))
      (if (pair? ps)
          (if (= (expm a (/ (- p 1) (car ps)) p) 1)
              (loop (+ a 1) fs) ; try next a
              (loop a (cdr ps)))
          (let loop ((m 1) (rs (list)))
            (if (= m p) (sort < rs)
              (if (= (gcd m (- p 1)) 1)
                  (loop (+ m 1) (cons (expm a m p) rs))
                  (loop (+ m 1) rs))))))))

We declare that a candidate a is not a primitive root if a(p−1/f) ≡ 1 (mod p), where f is one of the distinct factors of p − 1. Once we have a primitive root, we compute the rest by iterating m from 1 to p, computing am (mod p) for all m coprime to p. Here’s an example:

> (prim-roots 47)
(5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45)

You can run the program at https://ideone.com/VvYXUX.

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