# Example of calculating a primitive root for large prime?

I am trying to figure out how to calculate primitive root $w$ for a prime. Following what I read, I generated my prime to be 'safe prime', $p=qr+1$. I know $q$ (also prime) and $r$. Let's assume, for example: $q=11$, $r=8$ and $p=89$. Both $p$ and $q$ are prime, as needed.

I now find $w$ by choosing random number $h\mod p$ , take for example $h=41$: $$w=h^r\mod p\\w=41^8\mod 89=32$$

However, $32$ is not a primitive root for $89$. I know I am probably get something wrong, please help me find my mistake.

The first question to ask is "are you looking to find a primitive root (that is, a value $g$ such that $g^x \bmod p$ takes on all possible values in $\mathbb{Z}_p^*$), or are you looking to find a generator to the subgroup of order $q$?

Depending on what you are trying to do, either may make sense. If you are trying to get a subgroup for a DLog-based cryptosystem, the second may be what you want. On the other hand, sometimes we really want a primitive root.

The procedure you gave is a fine way to find a generator to the subgroup (assuming that you include a check that the value $w$ you get is not 1); however it is guaranteed not to give you a primitive root.

If you really want a primitive root, there are a couple of obvious possibilities:

• One is to pick a random value, and check if it happens to be a primitive root (which happens often enough to make this practical). This is easy if you know the factorization of $p-1$; that is, $x$ is a primitive root if, for all prime factors $s$ of $p-1$, we have $x^{(p-1)/s} \not\equiv 1 \pmod p$

• We can also do it be construction; for example, if $(p-1)/2$ is also prime (that is, $r=2$ in your formulation), and $p \equiv 3 \pmod 8$, then $w=2$ will always be a primitive root.

BTW: common usage nowadays is that a "safe prime" is a prime $p$ where $(p-1)/2$ is also prime (also known as a Sophie Germain prime). It used to have other meanings associated with it as well; however it's been a while since I've heard those other meanings used. Using the term now with a meaning other than what is common is likely to confuse people. If you need to use a different meaning, I'd suggest using different terminology.