# How to find a primitive cube root of unity

I would like some help to understand how to compute a distortion map and the result of a pairing.

I know that with this equation : $E : y^2 = x^3 + 1$ over some $\mathbb{F}_p$ we have a distortion map $\phi(x,y) = (\beta x, y)$.
I know that I need to find a primitive cube root of unity $\beta$ such that $\beta^3 = 1$ and it will give me a point in $\mathbb{F}_{p^2}$ with the form $a+bi$ with $a,b \in \mathbb{F_p}$
But I don't know how to compute this $\beta$.
Could you explain to me how to compute $\beta$ with a small example.

The paper "Pairings for Beginners" shows this example, how does he find $24i+29$ ?

Show the following.

1. For any prime $p \ne 3$, we have $p^2 \equiv 1 \pmod 3$, and thus a primitive $3$rd root of unity exists in $\mathbf F_{p^2}$.

2. Assuming $p^2 \equiv 1 \pmod 3$, for any $x \in \mathbf F_{p^2}^*$, $x^\frac{p^2-1}3$ is a $3$rd root of unity, and moreover, all $3$rd roots of unity can be obtained in this manner.

3. Given a $3$rd root of unity, it is easy to check whether it is primitive.

4. If $x$ is chosen uniformly from $\mathbf F_{p^2}^*$, $x^\frac{p^2-1}3$ is a primitive $3$rd root of unity with probability $2/3$.

• The equation $p^2 = 1 \mod 3$ is true for any number coprime to $3$, because $1$ is the only quadratic residue. – tylo Jul 27 '18 at 17:35
• @tylo Of course; I was just testing you. ;) – fkraiem Jul 27 '18 at 17:41
• Thank you for your answer but to be honest even with that I don't really understand how he got 24i + 29. Is there a way to find the roots without having to try all the $x \in \mathbb{F}_{p_2}$ ? I want to implement a distortion map in a pairing and it seems weird that I must compute several points especially if I have a very big p no ? – user1990088 Jul 27 '18 at 18:02
• Nobody said you need to try all the $x$. – fkraiem Jul 27 '18 at 18:07
• Then which x should I try ? – user1990088 Jul 27 '18 at 18:52