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