Programming ECC

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)-(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_{\mathrm{aP},\mathrm{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=lP=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+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}$.

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:

$$-(3x^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>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_{lP,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)-(-bP)-(-b-1)(O)$$

hence

$$(f_b{f}_{-b})=-[(bP)+(-bP)-2(O)]=-(g_{bP,-bP})$$

Thus

$$f_{a-b}=f_a{f}_{-b}{g}_{aP,-bP}/g_{(a-b)P,-(a-b)P}=\frac{f_a{g}_{aP,-bP}}{f_b{g}_{bP,-bP}{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.