Programming ECC - Miller's Algorithm

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 Z$ , we have $f_{a + b} (Q) = f_{a} (Q) f_{b} (Q) g_{a P, b P} (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.

set $f \leftarrow 1$ and $V \leftarrow P$
for $i \leftarrow t - 1$ to 0 do
1. set $f \leftarrow f^{2} g_{V, V} (Q) / g_{2 V, - 2 V} (Q)$ and $V \leftarrow 2 V$
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 $- λ X + Y + (- y + λ x)$ , where $λ = \frac{3 x^{2} + a}{2 y}$ .
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 $- λ X + Y + (- y_{1} + λ x_{1})$ where $λ = \frac{y_{2} - y_{1}}{x_{2} - x_{1}}$ .

It may be more efficient scale $λ$ 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 + (2 y) Y + (- 2 y^{2} + x (3 x^{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 > 2$ , then many divisions can be avoided since we may scale by quantities such as $2 y$ 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 > 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.

Ben Lynn blynn@cs.stanford.edu 💡

Miller’s Algorithm

The gP,Q functions

Contents

The $g_{P, Q}$ functions