2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user228113 Feb 27 '17 at 16:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Feb 27 '17 at 16:33
  • $\begingroup$ @ G.Sassatelli Yes, $p$ is prime. And thanks for that $\endgroup$ – lioness99a Feb 27 '17 at 16:33
  • $\begingroup$ 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\;$ $\endgroup$ – DonAntonio Feb 27 '17 at 16:46
  • $\begingroup$ @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}$ $\endgroup$ – lioness99a Feb 27 '17 at 16:53
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.