<s>[INST] find $x$ where $x^3$ $\equiv$ $1\mod p$, given a primitive root modulo of $p$ How to efficiently find $x$ where $x^3$ $\equiv$ $1\mod p$, given a primitive root of $p$ in the range of $[0,p-1]$?
$p$ is a prime.
Is is true that it only has three roots?
So if one of the primitive roots is given, how to efficient found all such x?
 [/INST] COMMENT (posted because is long for write as a comment).- There are three roots if and only if $p=3m+1$ and only a root if and only if $p=3m+2$.
Since $x^{p-1}-1=0$, if $x^3-1=0$ has three roots then
$\dfrac{x^{p-1}-1}{x^3-1}\in\mathbb F_p$ and if only one root (obviously equal to $1$) then $\dfrac{x^{p-1}-1}{x^3-1}\notin\mathbb F_p$.
Examples.-In $\mathbb F_{13}$ one has $\dfrac{x^{12}-1}{x^3-1}=(x^6+1)(x^3+1)$ and $x=1,3,9$
In $\mathbb F_{11}$ one has $\dfrac{x^{10}-1}{x^3-1}=x^7+x^4+x+\dfrac{1}{x^2+x+1}\notin\mathbb F_{11}[x]$ and just $x=1$
</s>