Primitive Root of a Prime I have a problem to solve that is the following,
I have a big prime number and i need to test if for example 2 is a primitive root a this big prime number, is there any easy way of doing this?
Thanks in advance.
 A: We answer the  question about $2$ and $19$ raised in a comment, and generalize somewhat. 
We want to know whether $2$ has order $18$ modulo $19$. If it doesn't, then $2^6\equiv 1\pmod{19}$ or $2^9\equiv 1\pmod{19}$. For the order of $2$ divides $18$, and if it is not $18$, it must divide $6$ or $9$. 
Note that $2^6=64\equiv 7\pmod{19}$. So $2^9\equiv 8\cdot 7=56\equiv -1\pmod{19}$, and we are finished: $2$ is a primitive root. 
In general, suppose that $p-1$ has the prime power factorization $p_1^{a_1}\cdots p_k^{a_k}$. Then if $a$ has order $\lt p-1$ modulo $p$, we must have 
that $a^{m_i}\equiv 1\pmod{p}$ for some $m_i$, where $m_i=\frac{p-1}{p_i}$.
If we can determine the primes that divides $p-1$ cheaply (a very big if!) then modular exponentiation can be used to settle the question of whether $a$ is a primitive root of $p$. Modular exponentiation is fast, even for large $p$, if we use the binary method. 
Added: Suppose that $d\lt p-1$ is the order of $a$ modulo $p$, where $p-1=p_1^{a_1}\cdots p_k^{a_k}$. Then $d=p_1^{b_1}\cdots p_k^{b_k}$
where some of the $b_i$ may be $0$, and $b_i\le a_i$ for all $i$, and $b_i\lt a_i$ for at least one $i$. 
In that case, $d$ divides $\frac{p-1}{p_i}$, and therefore if $a^d\equiv 1\pmod{p}$, we must also have $a^{(p-1)/p_i}\equiv 1\pmod{p}$. Thus to test whether some power of $a$ les than $p-1$ is congruent to $1$, we need only test the powers $\frac{p-1}{p_i}$. 
