<s>[INST] Most efficient way of calculating primitive cube roots of unity I understand the definition of a primitive cube root of unity in a finite field $\mathbb{F}_p$ to be all those numbers $x$ such that $x^3=1$ but $x\neq 1$ and $x^2 \neq 1$
When we have a small $p$, say $p=7$, we can compute these through 'brute force' - that is filling in the below table:
\begin{array}{|c|cccccc|}
\hline
x & x^1 & x^2 & x^3 & x^4 & x^5 & x^6\\
\hline
1 & \underline{\bf{1}} & 1 & 1 & 1 & 1 & 1\\
2 & 2 & 4 & \bf{\underline{1}} & 2 & 4 & 1\\
3 & 3 & 2 & 6 & 4 & 5 & \underline{\bf{1}}\\
4 & 4 & 2 & \underline{\bf{1}} & 4 & 2 & 1\\
5 & 5 & 4 & 6 & 2 & 3 & \underline{\bf{1}}\\
6 & 6 & \underline{\bf{1}} & 6 & 1 & 6 & 1\\
\hline
\end{array}
We then look along all the rows for any value of $x$ which has the first value of $1$ in the $x^3$ column; in this example we have the primitive cubed  roots of unity as $2$ and $4$ (first value of $1$ in each row is bold and underlined in the table above)
However this becomes unfeasible when $p$ becomes very big.
Can someone point me towards an easy method for computing the primitive cube roots of unity which requires as little computation as possible (eventually I will be implementing this in Python using values of $p$ several hundred digits long)
 [/INST] Perhaps I miss something here, but it all sums up to calculate the roots of $\;x^2+x+1=0\,\pmod p\;$ , and thus we have to know whether $\;-3\;$ is a quadratic residue, and then
$$\binom{-3}p=1\iff p=1\pmod3$$
Thus, for example in $\;\Bbb F_{17}\;$ there are no primitive roots cube roots of unity, but in $\;\Bbb F_{19}\;$ there are : $\;7\;,\;\;11\;$, obtained from the usual quadratic formula for $\;x^2+x+1=0\;$ :
$$\Delta=1-4=-3=16\pmod{19}\implies $$
$$x_{1,2}=\frac{-1\pm\sqrt{16}}2=\frac{-1\pm4}2=\begin{cases}-\frac52=-5\cdot10=-50=-12=7\pmod{19}\\{}\\\frac32=3\cdot10=30=11\pmod{19}\end{cases}$$
Observe that we also know, in general, that if $\;\omega\;$ is primitive cube root then also $\;\omega^2\;$ is, so if we know $\;7\pmod{19}\;$ is , then also $\;7^2=11\pmod{19}\;$ is
</s>