I am sure this question has been answered before but I could not find any similar question.

In Diffie-Hellman protocol implementations we can try to find a large primes using safe prime formula (i.e. $p = 2k + 1$ such that $k$ is a prime). So computer generates a relatively large prime $k$ and from that we get a prime (or pseudo-prime) $p$. To find a primitive root quickly, we generate a random number $x$ and test if $x, x^2, x^k \not\equiv 1 \bmod p$ if so then it is a primitive root (because the order of $\mathbb{Z}^*_p$ should divide $\phi(p)$).

My question is what is the success probability to generate a primitive root as there are $\phi(\phi(p))$ primitive roots modulo $p$. Thank you so much in advance.

  • $\begingroup$ For a safe prime you can simplify $\phi(\phi(p))$, and $x$ is between $1$ and $p$, so... $\endgroup$ – Dan Brumleve Mar 17 '17 at 2:26

\begin{align*} \phi(\phi(p)) &= \phi(p-1)&&\text{[since p is prime]}\\[4pt] &= \phi(2k)&&\text{[since $p = 2k + 1$]}\\[4pt] &= \phi(2)\phi(k)&&\text{[since $k$ is odd]}\\[4pt] &= k-1&&\text{[since $\phi(2)=1$ and $k$ is prime]}\\[4pt] \end{align*}

hence for $x$ randomly chosen in the interval $[2,p-2]$, the probability of success is

$$\frac{k-1}{p-3} = \frac{k-1}{2k-2} = \frac{1}{2}$$


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.