# Algorithm for finding modulo given primitive root.

It is conjectured by Artin that for every number $g$ which is not $-1$ and not a square number, there is an infinite number of $m$ such that $g$ is a primitive root modulo $m$.

How to find $m$ efficiently given primitive root $g$?

The reverse problem that given modulo $m$, find the primitive root $g$ can be solved faster than brute force with random trying with checking $g^{(m-1)/d} \neq 1$ ( $d\mid m$ ).

But I can't find something like that for this problem.

• Sorry, that first statement is not known. Well, as stated it is obviously false (take $g=1$ say). See Artin's Conjecture – lulu Apr 29 '18 at 20:08
• I'm sorry. I edit the statement .Thank you for pointing out. – Koreyuki Apr 29 '18 at 20:19