Pseudo-deterministic algorithms are randomized search algorithms which output unique solutions (i.e., with high probability they output the same solution on each execution). We present a pseudo-deterministic algorithm that, given a prime $p,$ finds a primitive root modulo $p$ in time $\exp(O(\sqrt{\log p \log \log p}))$. This improves upon the previous best known provable deterministic (and pseudo-deterministic) algorithm which runs in exponential time $p^{\frac{1}{4}+o(1)}.$ Our algorithm matches the problem's best known running time for Las Vegas algorithms which may output different primitive roots in different executions.

When the factorization of $p-1$ is known, as may be the case when generating primes with $p-1$ in factored form for use in certain applications, we present a pseudo-deterministic polynomial time algorithm for the case that each prime factor of $p-1$ is either of size at most $\log^c (p)$ or at least $p^{1/c}$ for some constant $c>0$. This is a significant improvement over a result of Gat and Goldwasser, which described a polynomial time pseudo-deterministic algorithm when the factorization of $p-1$ was of the form $kq$ for prime $q$ and $k= poly(\log p).$

We remark that the Generalized Riemann Hypothesis (GRH) implies that the smallest primitive root $g$ satisfies $g \le O(\log^6(p)).$ Therefore, assuming GRH, given the factorization of $p-1,$ the smallest primitive root can be found and verified deterministically by brute force in polynomial time.