Adleman and McCurley on 1994 published a paper 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 Z/pZ (p prime) generates the group. Is known that can be reduced to factorization and to discrete log (requieres ERH)

Shoup1990 (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? What we know about the complexity classes in what this problem belong?

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?