Recognition of a primitive root

Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz)

Problem 18 of this list of open problems is about testing if an element of $\mathbb{Z}/p\mathbb{Z}$, where $p$ is a prime, generates the group. It is known that this problem can be reduced to factorization and to discrete log (this reduction requires ERH).

Shoup 1990 (http://www.shoup.net/papers/primroots.pdf) gives a method that generates a subset of a finite field that contains at least one primitive root.

But what is known about checking if a element is a primitive root? What are the best algorithms for this? What do we know about the complexity classes in which this problem lies?

• I think narayanan at usc had something on this. – T.... Mar 15 '16 at 17:26
• The trivial approach is to factor $p-1$, and to check that for each prime factor $q$ of $p-1$, $a^{(p-1)/q} \not\equiv 1 \pmod{p}$. – Yuval Filmus Mar 15 '16 at 17:40