0

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.

Node.JS
  • 1,119

1 Answers1

1

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

quasi
  • 58,772