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


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

  • 1
    $\begingroup$ The equation $p^2 = 1 \mod 3$ is true for any number coprime to $3$, because $1$ is the only quadratic residue. $\endgroup$
    – tylo
    Commented Jul 27, 2018 at 17:35
  • $\begingroup$ @tylo Of course; I was just testing you. ;) $\endgroup$
    – fkraiem
    Commented Jul 27, 2018 at 17:41
  • $\begingroup$ 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 ? $\endgroup$ Commented Jul 27, 2018 at 18:02
  • $\begingroup$ Nobody said you need to try all the $x$. $\endgroup$
    – fkraiem
    Commented Jul 27, 2018 at 18:07
  • $\begingroup$ Then which x should I try ? $\endgroup$ Commented Jul 27, 2018 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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