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.
Programming Praxis 
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 []