# 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)

• Is $p$ prime? However, for a prime $p\ne2$, the fact that $x^3-1=(x-1)(x^2+x+1)$, yields that it sums up to the calculation of $2^{p-2}\cdot\left(-1\pm\lambda\right)$, where $\lambda^2=-3\pmod p$. Though you do not really gain much in running time in comparison to your first guess. – user228113 Feb 27 '17 at 16:26
• I don't have an answer to your question, but note that when you find $a\in \mathbb F_p$ to be a primitive cube root of unity, then the other cube root is $a^2$, and you don't need to search through $a+1, a+2,\ldots$ etc. Also, before doing any work, it is worth checking in the field has cube roots of unity (other than $1$) in it. This is "easy" to check since $p-1$ must necessarily be a multiple of $3$. If $p$ is known as in terms of its base-10 representation, the test is easy to carry out, If $p$ is known only in base-2 representation, it is a little more complicated. – Dilip Sarwate Feb 27 '17 at 16:33
• @ G.Sassatelli Yes, $p$ is prime. And thanks for that – lioness99a Feb 27 '17 at 16:33
• 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\;$ – DonAntonio Feb 27 '17 at 16:46
• @DonAntonio Could you expand on that a bit please - I understand what a quadratic residue is but I don't see how you got $7$ and $11$ from it in $\mathbb{F}_{19}$ – lioness99a Feb 27 '17 at 16:53

## 1 Answer

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

• Thanks, this makes a lot more sense now! – lioness99a Feb 28 '17 at 8:39