What is a primitive root? So I'm trying to learn about RSA and have come across various subtopics, including the discrete logarithm problem. 
This mentions primitive roots, which I do not understand.
Essentially all I want is an answer in simple terms of what a primitive root actually is.
Thanks
 A: I sometimes find it helpful to think of primitive roots as akin to logarithms...that is, a way to change multiplication into addition.  For example, let's consider powers of $3$ mod$(17)$.  They are: $$\{3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1\}$$
We note there are $16$ distinct values, so $3$ is indeed a primitive root mod$(17)$.  We now ask, for each residue class $i$, what power of $3$ gives $i$ mod$(17)$?  By inspection these "logarithms" are:
$$\{16, 14, 1, 12, 5, 15, 11, 10, 2,3, 7, 13, 4,9,6,8\}$$
That is to say, $$3^{16}=1,\;\;3^{14}=2,\;\; 3^1=3,\;\;...$$
Now say you want to multiply $8$ by $13$ mod$(17)$.  We read off that $8=3^{10}$ and $13=3^4$  so $8*13=3^{14}=2$.
In this way, if you have a primitive root and you have a look up table for the "logarithms" then you can always reduce multiplication to addition.  Of course, it isn't all that easy to find primitive roots.
A: Let $n>1$ be a natural number.
Let $S$ be the set of numbers coprime to $n$. A number $m$ is called a primitive
root in $\mathbb Z_n$, if the Set $\{m,m^2,m^3,...,m^{\phi(n)}\}$ modulo $n$ contains
every element of $S$.
$\phi(n)$ is the Euler-Phi-Function : The number of $m's$ with $gcd(m,n)=1$
Example : $n=10$ 
Numbers coprime to $10$ : $\{1,3,7,9\}$
The elements $3,3^2,3^3,3^4$ are congruent $3,9,7,1$ modulo $10$, so all the
numbers occur. Hence, $3$ is a primitve root in $\mathbb Z_{10}$
