What is a primitive root?

Question

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

Answer 1

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.

Answer 2

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}$