Elliptic Curves

Suppose we are working on a curve $E$ over ${𝔽}_q$ with security multiplier $k$ such that $E[l]$ is contained in $E/{𝔽}_q^k$.

$e(P,Q)=f_P({𝒜}_Q{)}^{(q^k-1)/l}$

where ${𝒜}_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/{𝔽}_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)-(\mathrm{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,...,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$
  • end
• end

At the end, $f=f_l(Q)=f_P(Q)=e(P,Q)$, and $V=lP$.

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+\mathrm{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.