Miller’s Algorithm

Consider $E[l]$, the $l$-torsion points of an elliptic curve $E$. Write $f_P$ for the rational function with divisor $l(P)-l(O)$.

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) - (c P) - (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 ,..., l_0$. Then Miller’s algorithm computes $f_P(Q)$ as follows.

  1. set $f \leftarrow 1$ and $V \leftarrow P$

  2. for $i \leftarrow t-1$ to 0 do

    1. set $f \leftarrow f^2 g_{V,V}(Q)/g_{2V, -2V}(Q)$ and $V \leftarrow 2V$

    2. if $l_i = 1$ then

      1. set $f \leftarrow 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)$, and $V = l P = O$.

By adding extra logic in the above algorithm, we can avoid handling points of infinity when computing the $g$ functions. On the last iteration, we know $V = -P$ if $l$ is odd, and $V$ has order 2 if $l$ is even.

The $g_{P,Q}$ functions

Let the curve be $Y = X^3 + a X + 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}$.

It may be more efficient scale $\lambda$ appropriately and do all the divisions at once. If the embedding degree is at least two, and $P, Q$ are in the base field, the Tate exponentiation will get rid of any scaling factors. If the embedding degree is one, then since one has to compute $f(Q+R)/f(Q)$ (which should be computed with one iteration of Miller’s algorithm), the scaling factors in the numerator cancel those in the denominator. Thus the functions may be scaled as follows:

  • Tangents:

\[ -(3 x^2 + a)X + (2y) Y + {({-2y^2 + x(3x^2 + a)})} \]
  • Verticals:

\[ X + (-x) \]
  • Lines:

\[ (y_1 - y_2)X + (x_2 - x_1)Y + (x_1 y_2 - x_2 y_1) \]

(TODO: move to optimizations page since it assumes we’re using Tate. mention projective coords and mixin) If $P$ lies in the ground field and $k \gt 2$, then many divisions can be avoided since we may scale by quantities such as $2y$ and $x_2 - x_1$ in the above equations. These quantities lie in the ground field hence become 1 during exponentiation.

Note

\[ f_{l+1} = f_l f_1 \frac{g_{l P, P}}{g_{-(l + 1)P, (l+1)P}} = f_l \frac{g_{O, P} }{ g_{-P,P}} = f_l \]

that is, $f_l = f_{l+1}$, hence if $l = 2^s - 1$, we can easily compute $f_l(Q)$ using basically $s$ squarings. For Solinas primes of the form $l = 2^a + 2^b - 1$ (where $a \gt b$), computing $f_{2^b}(Q)$ is an intermediate step in computing $f_{2^a}(Q)$, and then we may simply use one of the above formulas to compute $f_{2^a + 2^b}(Q) = f_{l+1}(Q) = f_l(Q)$.

Sometimes we need to compute $f_{a-b}$. First note

\[ (f_{-b}) = -b(P) - (-b P) - (-b - 1)(O) \]

hence

\[ (f_b f_{-b}) = -[ (b P) + (-b P) - 2(O) ] = - (g_{b P, -b P}) \]

Thus

\[ f_{a-b} = f_a f_{-b} g_{a P,-b P} / g_{(a-b)P, -(a-b)P} = \frac{f_a g_{a P, -b P}}{f_b g_{b P, -b P} g_{(a-b)P, -(a-b)P}} \]

Under certain conditions(described later), then we have $f_{l-1} = f_l$ so the last iteration of Miller’s algorithm can be simplified.