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.

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: