How to find a primitive cube root of unity

Question

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$ ?

Thank you for your answers

Answer 1

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$.