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,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.
then r^x (mod p) goes through all the numbers 1...(p-1) in some order.
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,...
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.