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)  (c1)(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 t1\) 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.