## 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

### 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 []
```