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


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 Jul 27 '18 at 17:35
  • $\begingroup$ @tylo Of course; I was just testing you. ;) $\endgroup$ – fkraiem Jul 27 '18 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$ – user1990088 Jul 27 '18 at 18:02
  • $\begingroup$ Nobody said you need to try all the $x$. $\endgroup$ – fkraiem Jul 27 '18 at 18:07
  • $\begingroup$ Then which x should I try ? $\endgroup$ – user1990088 Jul 27 '18 at 18:52

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.