Primitive roots

This text concentrates on primitive roots of primes, just for practical purposes. From elementary number theory we know, that for all integers a, when p is prime (and a is positive and less than p)

a^(p-1)=1 (mod p)

(From now on we just might suppose that the modulus p is prime). For all primes there exists a primitive root r (actually many). A primitive root r is a number, that

when x goes from 1 to p-1,
then r^x (mod p) goes through all the numbers 1...(p-1) in some order.

The order of a root r is the smallest positive x for which r^x = 1 (mod p). So the order of a primitive root (modulo a prime p) is p-1.

Since a^(p-1)=1 (mod p) always, it is obvious that if the order of a is less than p-1, the order should divide p-1. To see this, notice that when you start multiplying 1*a*a*a*... (mod p) when the result of the multiplication is 1, the sequence starts over again. And when you have done the multiplication p-1 times, the result must be 1. So the order of a must divide p-1.

To test whether a number a is a primitive root modulo p, we want to know whether the order of a is p-1 or less. The first thing to do is to factor p-1. This can be done effectively (when p < 2^32) with a precalculated table of primes less than 2^16 and simple trial division. Then if

a^((p-1)/f) != 1 (mod p)

for all factors f of p-1, a is a primitive root modulo p. Note that one only has to do the test for all prime factors of p-1. There's no need to check if a to any smaller power is 1, since raising the 1 to some higher power is still 1, so one can just check the highest possible powers.

There are lots of primitive roots for all primes, so finding one by directly testing numbers should not be too difficult. An easy approach is to test prime numbers a=2, 3, 5, 7,...

An example:

Let p=2^32-2^20+1. Then p is of the form k*n+1, that is needed for doing number theoretic transforms upto length n=2^20. The factorization of p-1 is

p-1=2^20*3^2*5*7*13.

Now start testing numbers a=2, 3, 5, 7,... and see if

a^((p-1)/2) != 1 (mod p)
a^((p-1)/3) != 1 (mod p)
a^((p-1)/5) != 1 (mod p)
a^((p-1)/7) != 1 (mod p)
a^((p-1)/13) != 1 (mod p)

(the first a for which this should occur is a=19).

A root w of order n (that is, w^n=1 (mod p)), can be calculated with w=r^k (mod p), when p=k*n+1. Note that now w^(n/2) = -1 (mod p), so the decomposition of the number theoretic transform to a fast number theoretic transform really works (just like the FFT). To see this, note that w^n = 1 (mod p), and so w^(n/2) = +1 or -1 (mod p). But w^(n/2) can't be 1, since then w would be a root of order n/2, and it isn't.

Back to number theoretic transforms.