Computing the Tate Pairing
Suppose we are working on a curve \(E\) over \(\mathbb{F}_q\) with security multiplier \(k\) such that \(E[l]\) is contained in \(E / \mathbb{F}_q^k\).
where \(\mathcal{A}_Q\) is a divisor equivalent to \((Q) - (O)\). and \((f_P) = l(P) - l(O)\). For a supersingular curve with \(k > 1\), we may simplify this to \(e(P,Q) = f_P(Q)^{(q^k - 1)/l}\) provided \(P \in E/\mathbb{F}_q\).
Miller’s Algorithm
Let \(g_{P,Q}\) be the line between the points \(P\) and \(Q\), and let \(f_c\) be the function with divisor \((f_c) = c(P) - (cP) - (c-1)(O)\). Then for all \(a,b \in \mathbb{Z}\), we have \(f_{a+b}(Q) = f_a(Q) f_b(Q) g_{aP,bP}(Q) / g_{(a+b)P, -(a+b)P}(Q)\). Let the binary representation of \(l\) be \(l_t ,..., t_0\). Then Miller’s algorithm is the following:
-
set \(f \leftarrow 1\) and \(V \leftarrow P\)
-
for \(i \leftarrow t-1\) to 0 do
-
set \(f \leftarrow f^2 g_{V,V}(Q)/g_{2V, -2V}(Q)\) and \(V \leftarrow 2V\)
-
if \(l_i = 1\) then set \(f = f g_{V,P}(Q)/g_{V+P, -(V+P)}(Q)\) and \(V \leftarrow V + P\)
-
At the end, \(f = f_l(Q) = f_P(Q) = e(P,Q)\), and \(V = l P\).
Note on implementation: by adding extra logic in the above algorithm, one can avoid handling points of infinity when computing the \(g\) functions.
The \(g_{P,Q}\) functions
Let the curve be \(Y = X^3 + aX + b\).
-
Tangents: At the point \((x,y)\), the line describing the tangent at that point is \(-\lambda X + Y + (-y + \lambda x)\), where \(\lambda = \frac{3x^2 + a}{2y}\).
-
Vertical lines: These are lines between \(P\) and \(-P\). Let \(P=(x,y)\). Then the vertical line through \(P\) is \(X + (-x)\).
-
Other lines: The line between \(P=(x_1, y_1)\) and \(Q=(x_2, y_2)\) is given by \( - \lambda X + Y + (-y_1 + \lambda x_1)\) where \(\lambda = \frac{y_2 - y_1}{x_2 - x_1}\).
In implementations, it may be more efficient scale \(\lambda\) appropriately and do all the divisions at once.