The Tate pairing

Suppose that P and Q are points on an elliptic curve and that the order of P is n. Let f_P be a rational function equivalent to n(P) – n(O) and D_Q be the divisor (Q) – (O). Then the Tate pairing of P and Q is e(P, Q) = f_P(D_Q).

We know how to get f_P and how to evaluate it at a divisor, but the fact that evaluating f_P at the divisor (Q) – (O) would require evaluating f_P at the point O causes trouble. But if R is another point not equal to O, it turns out that we get the same answer when we evaluate f_P at (Q + R) – (R) as we do when we evaluate f_P at (Q) – (O). This means that we can find e(P, Q) by doing the following:

1. Find f_P as we described previously.
2. Pick a random R.
3. Calculate e(P, Q) = f_P(Q + R) / f_P(R).

That’s all there is to it. When I first heard about the use of the Tate pairing in Boneh-Franklin identity-based encryption, for example, I used this very approach to implement the Tate pairing in Mathematica, and it was good enough for that purpose. There are lots of ways to make this calculation more efficient, but for small values of n, what we’ve described is fairly simple to implement.