7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think narayanan at usc had something on this. $\endgroup$
    – Turbo
    Commented Mar 15, 2016 at 17:26
  • 3
    $\begingroup$ 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}$. $\endgroup$
    – Yuval Filmus
    Commented Mar 15, 2016 at 17:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.