Finding Primitive Roots Pseudo-Deterministically.
Ofer Grossman · Electronic colloquium on computational complexity · 2015
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( p log p log log p)). This improves upon the previous best known provable deterministic (and pseudo-deterministic) algorithm which runs in exponential time p 1 4+o(1). Our algorithm matches the problem’s best known running time for Las Vegas algorithms which may output di↵erent primitive roots in di↵erent 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 logc(p) or at least p1/c for some constant c > 0. This is a significant improvement over a result of Gat and Goldwasser [5], 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 O(log(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.