1
$\begingroup$

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.

Thank you for your time!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.