Miller's Algorithmの定義の読み方

Miller's Algorithm の定義

Ben Lynn のウェブサイトで 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) - (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_{aP,bP} (Q) g_{(a+b)P, -(a+b)P} (Q)$. Let the binary representation of $l$ be $l_t,\cdots,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)$ anf $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$

---

前提

• 楕円曲線の式は、変数が $x, y$ で、coefficient が finite field (以後 F) の要素の polynomial ring (以後 R)。例えば、BLS12-381 の G1 だと、$y^2 = x^3 + 4$ で、$x,y$ の coefficient と $4$ が $F_q$ の要素。

• 楕円曲線上の点は、楕円曲線の式を満たす F の要素 $x,y$ の組み合わせ。

読み方

• $E[l]$: 位数が $l$ の点の集合

• Function: R の要素の比 (rational function)。点を入力に取って、比の式の $x,y$ を点の $x,y$ で置き変えることで評価できる。評価結果は F の要素。

• Divisor: function のふるまいを表すもの。プラスの項はゼロになる点、マイナスの項は評価不能になる点 (pole) を表す。係数はそれぞれ項の multiplicity。より具体的には、$g(x,y)$ が、点 $P$ でゼロや評価不能にならない関数で、$xP$ が $P$ の $x$ 座標だとして、$f_P$ の divisor が $l(P)$ を含んでいる場合は、$f_P(x,y)=(x - xP)^l g(x,y)$ のように、$xP$ が関数のルートになる項が $l$ 個含まれている。

• $g_{P,Q}$: 点 $P,Q$ を通る直線の式 $y = mx + b$ の右辺の項を左辺に移項した $y - mx - b = 0$ の左辺が分子で、分母が $1$ の rational function。$m$ は直線の傾きで、$b$ は $y$ 切片。通常の関数と同じように、点を入力として、F の要素に評価できる。

• $f_c$: $c(P) - (cP) - (c-1)(O)$ という divisor を持つ rational function。 $c$ は F の要素。divisor の定義内の $c$ が、$f_c$ の $c$ で置き変わる。

• $f_c(Q)$: $f_c$ を、点 $Q$ で評価する。評価結果は、F の要素。

• $g_{A,B}(Q)$: $g_{A,B}$ を、点 $Q$ で評価する。評価結果は、F の要素。

• $l_t,\cdots,l_0$: $l$ を binary で表したビットベクター。例えば、[1,0,0,...,1] 。