Finding Primitive Roots Pseudo-Deterministically

摘要

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 ( log p log log p )) . This improves upon the previous best known provable deterministic (and pseudo-deterministic) algorithm which runs in exponential time p 4 1 + 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 0"> 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 k q for prime q and k = p ol y ( log p ) We remark that the Generalized Riemann Hypothesis (GRH) implies that the smallest primitive root g satisfies g 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.