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

<p>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).</p>

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

<p>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?</p>

CC BY-SA 3.0
2016-03-15T17:26:25.400Z
I think narayanan at usc had something on this.
Turbo
CC BY-SA 3.0
2016-03-15T17:40:59.947Z
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
<cc.complexity-theory><reference-request><nt.number-theory><algebraic-complexity><gr.group-theory>
Recognition of a primitive root
ricardorr
# Recognition of a primitive root

(Asked by: username_0 on 2016-03-15)

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?

**Tags:** cc.complexity-theory, reference-request, nt.number-theory, algebraic-complexity, gr.group-theory
> **Comments:**
> **username_1**: I think narayanan at usc had something on this.  
> **username_2**: 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}$.  

---

## 0 answers

