pairing_math.tex

\chapter{ペアリング}
\label{chap:pairing_math}
この章ではペアリングの定義と具体的な計算式について説明します。
少々準備が多いのですが一つずつ確認していきましょう。

\section{関数の零点と極}
複素数体$\CC$上の0でない関数$f(x)$を考えます。
$f(x)=0$となる$x=a$を$f$の零点といいます。
$f_i \in \CC$（$i=0, 1, \dots$）を定数として
\[
f(x)=\sum_{i=0}^\infty f_i (x-a)^i=f_0 + f_1 (x-a) + f_2 (x-a)^2 + \cdots
\]
と書けるとします（$f$の$x=a$におけるLaurent（ローラン）級数といいます）。
$f(a)=0$なので$f_0=0$です。
$f_i \ne 0$となる最小の$i$を$f$の$x=a$における零点の位数といい
\[
\ord{a}{f}:=i
\]
と書きます。
たとえば$f(x)=x^3$のとき、零点は$x=0$で$\ord{0}{x^3}=3$です。
位数はその点で関数$f$と$x$軸がどのように接しているかを表しています。
直線$y=x$と直線$y=0$は原点$(0,0)$で交差しています。
関数$y=x^n$は$x$軸と$(0,0)$で$n$重に接しているといいます。
\image{zero.pdf}{関数の零点とその位数}
$f(x)=x(x+1)(x-1)^2$だと零点は$x=0, -1, 1$の3個です。
$x=0$での位数は
\[
f(x)=x-x^2-x^3+x^4
\]
なので$\ord{0}{f}=1$。
$x=1$での位数は
\[
f(x)=2(x-1)^2+3(x-1)^3+(x-1)^4
\]
と変形できるので$\ord{1}{f}=2$。
$x=-1$での位数は
\[
f(x)=-4(x+1)+8(x+1)^2-5(x+1)^3+(x+1)^4
\]
と変形できるので$\ord{-1}{f}=1$です。
いちいち式変形しなくても、たとえば$x=1$に十分近いところでは$x(x+1)$は2にとても近いので
\[
f(x) \approx 2(x-1)^2
\]
と考えると$\ord{1}{f}=2$だとわかります。一般に$x=a$の付近で$f(x) \approx c(x-a)^n$（$c$は定数）の形になるなら
$\ord{a}{f}=n$となります。

もし$f(x) \approx c(x-a)^n$の$n$が負ならどうなっているのでしょう。
$x \rightarrow a$で$f(x)$は無限大になります。\index{きょく@極}
このとき$x=a$は$f$の極といい、$\ord{a}{f}:=n$とします。

より正確にいうと次の通りです。
関数$f(x)$が整数$n$と
$f_i \in \CC$（$i=-n, -n+1, \dots$）を定数、ただし$f_{-n}\ne0$として
\[
f(x)=\sum_{i=-n}^\infty f_i (x-a)^i=\frac{f_{-n}}{(x-a)^n} + \frac{f_{-n+1}}{(x-a)^{n-1}} + \cdots
\]
と書けるとします。$n>0$のとき$f$は$x=a$で$n$位の極を持つといいます。
$n<0$のときは$f$は$x=a$で$(-n)$位の零点を持ちます。
$n=0$のときは関数$f$は$x=a$で普通の値$f_0\ne0$をとり、
$\ord{a}{f}:=0$と定義しましょう。

関数の中にはたとえば$f(x)=e^{1/x}=\sum_n 1/n! (1/x)^n$のような$x=0$での位数がマイナス無限大になってしまうものがあります。
そのような関数はここでは考えません。関数$e^{1/x}$における$x=0$は真性特異点といわれます。

なお、零点や極の位数は有限体上の関数に対しても別の手法を用いて定義されます。
\section{位数の性質}
関数の零点や極の位数の性質を調べましょう。
まず関数$f$が$x=a$で位数$n$の零点を持つなら関数$1/f$は$x=a$で位数$n$の極を持ちます。
\[
\ord{a}{f}=-\ord{a}{1/f}.
\]

また2個の関数$f$、$g$の点$a$における位数を$n$、$m$とします。
つまり
\[
f(x):=\sum_{i=n}^\infty f_i (x-a)^i, \quad g(x):=\sum_{i=m}^\infty g_i (x-a)^i, \quad f_i, g_i \in \CC.
\]
すると2個の関数の積$fg$は$f_n g_m(x-a)^{n+m} \ne 0$から始まります。
つまり
\[
\ord{a}{fg}=\ord{a}{f}+\ord{a}{g}
\]
が成立します。

2個の関数の和の位数はどうなるでしょう。$n$と$m$が異なれば小さい方の位数になります。
たとえば$f(x)=x^3$, $g(x)=x^5$なら$(f+g)(x)=x^3+x^5$なので$\ord{0}{f+g}=3$。
位数が同じときは係数が打ち消しあって、もっと大きい値の位数になることがあります。
たとえば$f(x)=x^3+x^4$, $g(x)=-x^3+x^5$なら$\ord{0}{f+g}=\ord{0}{x^4+x^5}=4$。
つまり一般に
\[
\ord{a}{f+g} \ge \min(\ord{a}{f},\ord{a}{g})
\]
が成立します。

よってたとえば点$x=a$で位数$n$以上の零点（あるいは極）を持つ関数の集合$V$を考えると、
$V$の2個の元を足したり引いたりしても$V$の元になることがわかります。
ここで定数関数$f=0$はどの点でも位数無限大と解釈することにして、$V$の元とみなします。
すると$V$は$f=0$を単位元、関数の足し算を演算とする加法群になります。
関数を定数（$\ne 0$）倍しても、その位数は変わらないので$V$は$\CC$ベクトル空間になります。

\section{楕円曲線上の関数の零点と位数の例}
前節で定義した関数の零点や極の位数は楕円曲線上の関数に対しても考えることができます。
定義方程式$y^2=x^3+ax+b=(x-e_1)(x-e_2)(x-e_3)$（$e_i$は互いに異なる）の楕円曲線を$E$とします。
\[
E \ni P=(x,y) \mapsto y
\]
という関数を考えます。$E$上の点$P=(x,y)$に対してその$y$座標を返す関数です。
本来なら$f_1$といった名前をつけるところですが、$y$という名前にします。
座標と関数を同じ記号で書くのはわかりにくいかもしれませんが、慣れると自然に扱えます。

関数$y$の値が0になるのは$P_i:=(e_i,0)$（$i=1,2,3$）のときのみです。
点$P_1$の付近での関数$y$の挙動を観察するために、$s:=x-e_1$としましょう。
すると
\[
y^2=((s+e_1)-e_1)((s+e_1)-e_2)((s+e_1)-e_3)=s(s+e_1-e_2)(s+e_1-e_3)
\]
です。$e_1-e_2, e_1-e_3 \ne 0$で$s$が0にとても近いときは$y^2= cs$とみなせます。
ここで$c$は$c:=(e_1-e_2)(e_1-e_3)\ne 0$という定数です。
つまり点$P_1$の付近で楕円曲線$E$の方程式は$y^2=c(x-e_1)$と近似でき、非常に小さいパラメータ$t$を用いて$P_t:=(t^2/c+e_1,t) \in E$と表現できます。
このとき$y$座標の値を返す関数$y$は$t$そのものになります。
\image{ec-zero.pdf}{点$P_1$付近でのパラメータ$t$による表示}
$P_1$の付近では$t=0$なのでその位数は1です。
$P_2$, $P_3$についてもそれぞれの点の付近でパラメータをとって考えると同様に位数は1です。
よって$\ord{P_i}{y}=1$。

別のパラメータ、たとえば$t$の代わりに$t^3$を使うと位数が3になってしまい、位数は一意に決まらないのではないかと思われるかもしれません。
ここで使うパラメータは局所座標（\ref{projective}節参照）と呼ばれ、実際には滑らかな逆写像が存在しなければならないなどのいくつかの制約があります。
その制約により$t^3$のようなものは局所座標とはならず、位数は一意に決まることが知られています。

関数$y$に極はあるのでしょうか。楕円曲線$E$は無限遠点$O$を持っているのでした。
$O$は$y$が無限大になったときとみなせるので$O$が$y$の極になります。
その位数はいくつでしょう。
$y$が大きくなると$x$も大きくなり、
\[
y^2=x^3+ax+b=x^3\left(1+\frac{a}{x^2}+\frac{b}{x^3}\right) \approx x^3
\]
と近似できます。つまり$E$は$O$の付近でパラメータ$t$（先程の$t$とは別物）を用いて$(t^2,t^3)$と表現できます。
関数$y$は$y=t^3$となるので$\ord{O}{y}=-3$です。

もう一例あげておきましょう。
\[
E \ni P=(x,y) \mapsto x - e_i
\]
を考えます。関数$y$と同じく$x-e_i$を関数表記でも使います。
$x-e_i$が0になるのは$P=P_i$のときです。
点$P_1$の付近で$E$上の点を$(t^2/c+e_1,t)$と表現すると、
$x-e_1=t^2/c$となります。よって$t=0$の付近を考えると$\ord{P_i}{x-e_i}=2$。
極は関数$y$と同じく無限遠点$O$です。
$O$の付近では大きな$t$を用いて$(t^2,t^3)$と表現できたので$\ord{O}{x-e_i}=-2$となります。
\section{因子}
これから関数とその零点と極の関係を見るために因子（divisor）という概念を導入します。

楕円曲線$E$上の因子$D$とは$E$上の有限個の点$P_1, P_2, \dots \in E$の整数個（$n_1, n_2, \dots \in \ZZ$）の形式的な有限和
\[
D:=\sum_i n_i (P_i)
\]
のことです。たとえば$2(P)$とか$3(Q)-2(O)$などが因子です。
$2P$や$3Q-2O$と書いてしまうと、楕円曲線上の点の加法と間違えてしまうので点には括弧をつけています。

2個の因子$D_1=\sum_i n_i (P_i)$と$D_2:=\sum_i m_i (Q_i)$があったとき、因子の和$D_1+D_2$を
\[
D_1+D_2:=\sum_i n_i (P_i)+\sum_i m_i (Q_i)
\]
と定義します。単に形式的に2個の因子の要素を並べただけです。
$P_i$や$Q_i$に同じ点がある場合はその係数を足すことにします。
たとえば$2(P) + 3(P)=5(P)$。$(3(Q)-2(O)) + (4(O) - (P)) = -(P) + 3(Q) + 2(O)$となります。

和が空っぽのときの因子を$D=0$と書くと、因子全体の集合は$0$を単位元、上記の因子の和を演算として加法群になります。
因子$D=\sum_i n_i (P_i)$の逆元$-D$は$\sum_i -n_i (P_i)$ですね。

ある関数$f$が点$P_i$で位数$n_i$の零点、点$Q_j$で位数$m_j$の極を持っているとき、$f$に対応する因子
$\Div(f)$を
\[
\Div(f):=\sum_i n_i (P_i) - \sum_j m_j(Q_j)
\]
と定義します。$\Div(f)$を主因子（principal divisor）といいます。
たとえば前節の楕円曲線$E$上の関数$y$や$x-e_i$に対応する因子は
\begin{align*}
&\Div(y)=(P_1)+(P_2)+(P_3) - 3(O),\\
&\Div(x-e_i)=2(P_i)-2(O)
\end{align*}
です。
\section{楕円曲線上の関数の主因子の性質}
さて、楕円曲線上の関数の主因子には著しい性質があります。
\begin{theorem}\label{div_func}
$f$を楕円曲線上の0でない関数、その主因子を$\Div(f)=\sum_i n_i (P_i)$とすると、
\begin{align*}
&\sum_i n_i = 0,\\
&\sum_i n_i P_i = O
\end{align*}
が成立する。
逆に、ある因子$D=\sum_i n_i (P_i)$がこの2個の等式を満たすとき、
$\Div(f)=D$となる$f$が定数倍を除いてただ一つ存在する。
特に$D=0$という因子を考えると零点も極も持たない関数は0でない定数関数に限る。
\end{theorem}

ここで一つ目の式の和は$f$の零点や極の位数の和、つまり整数の足し算です。
一般に因子$D=\sum_i n_i (P_i)$に対してその次数を$\deg(D):=\sum_i n_i$と定義します。
一つ目の式は関数$f$に対して
\[
\deg(\Div(f))=0
\]
を意味します。

二つ目の和は楕円曲線上の点の加法による和です。
これは関数の零点や極が$n$個あるとき、$n-1$個の点の位置を決めると、残りの点の位置が決まってしまうことを意味しています。
零点や極という局所的な性質が、関数の全体の形を決めてしまうのは興味深いです。
残念ながらここでは準備が多すぎてこの定理の証明はできません。

それでいくつかの例についてこの定理の前半が成立していることを確認するのに留めます。
関数$y$に対して$\Div(y)=(P_1)+(P_2)+(P_3)-3(O)$でした。よって
\[
\deg(\Div(y))=1+1+1-3=0.
\]
点$P_i$は楕円曲線$E$と直線$y=0$との交点なので、楕円曲線の加法の定義から$P_1+P_2=-P_3$。
よって
\[
P_1+P_2+P_3-3O=O
\]
となり二つ目の式も成立しています。

また関数$x-e_i$についても$\Div(x-e_i)=2(P_i)-2(O)$でした。よって
\[
\deg(\Div(x-e_i))=2-2=0.
\]
点$P_i$は楕円曲線$E$と直線$x=e_i$との接線なので
$2P_i=O$。よって
\[
2P_i-2O=O
\]
より定理が成立していることを確認できます。

もう一つ、定理を紹介しましょう。
まず記号の定義をします。
関数$f$と因子$D=\sum_i n_i (P_i)$に対して
\[
f(D):=\prod_i f(P_i)^{n_i}
\]
とします。たとえば$f(x)=x^2$, $D=(3)+2(-1)$なら$f(D)=f(3)f(-1)^2=9 \cdot 1^2=9$です。
\begin{theorem}[Weil相互法則（Weil reciprocity law）]\label{weil_reciprocity}
楕円曲線上の関数$f$, $g$について
\[
f(\Div(g))=g(\Div(f))
\]
が成立する。
\end{theorem}
ここで一般の証明はできませんが$\RR$上の単なる多項式のときに観察します。
$f(x):=\prod_i(x-a_i)^{n_i}$, $g(x):=\prod_j(x-b_j)^{m_j}$とします。
ただし$x \rightarrow \infty$で発散しないように$\sum_i n_i = \sum_j m_j = 0$とします。
すると、
\[
\Div(f)=\sum_i n_i (a_i), \quad \Div(g)=\sum_j m_j (b_j)
\]
となります。よって
\begin{align*}
f(\Div(g))&
 =\prod_j f(b_j)^{m_j}=\prod_j \left(\prod_i(b_j-a_i)^{n_i}\right)^{m_j}
 =\prod_{i,j} (b_j-a_i)^{n_i m_j}\\
 &=\left(\prod_{i,j}(a_i-b_j)^{n_i m_j}\right) \prod_{i,j}(-1)^{n_i m_j}\\
 &=g(\Div(f))(-1)^{\sum_{i,j}n_i m_j}
 =g(\Div(f))(-1)^{(\sum_i n_i)(\sum_j m_j)}=g(\Div(f)).
\end{align*}
\section{ペアリング}
楕円曲線$E$に対して$E[m]:=\Set{P \in E|mP=O}$とします。点$P \in E[m]$を$m$等分点（またはねじれ点）といいます。
$\lambda_1,\lambda_2\in\CC$で定まるトーラスを考えると
$E[m]=\Set{(i/m)\lambda_1+(j/m)\lambda_2|0 \le i, j < m}$で$m$等分点は$m^2$個あります。
\image{mtorsion.pdf}{トーラスにおける$4$等分点の集合$E[4]$}
有限体$\FF_p$上の楕円曲線$E$でも$m$が$p$の倍数でないとき$E[m]$は$m^2$個の元からなります。
ただしそれらの点の座標は一般に$\FF_p$の元ではなく、その拡大体の元となります。

点$P \in E[m]$に対して$D_P:=m(P)-m(O)$という因子を定義します。
$\deg(D_P)=0$かつ$mP=O$なので定理\ref{div_func}より$\Div(f_P)=D_P$となる関数
$f_P$が存在します。

\index{ぺありんぐ@ペアリング}

体$k$上の楕円曲線$E/k$と自然数$m$をとります。
ただし$p:=\Char(k)>0$のときは$m$は$p$の倍数でないとします。
Weil（ヴェイユ）ペアリング\index{Weilぺありんぐ@Weilペアリング}
\[
e:E[m] \times E[m] \rightarrow \overline{k}
\]
を次の方法で定義します。

点$P, Q \in E[m]$に対して$\Div(f_P)=D_P$, $\Div(f_Q)=D_Q$となる関数をとります。
適当な$S \in E[m]$に対して、
\[
e(P, Q):=\frac{f_P(Q+S)}{f_P(S)} \cdot \frac{f_Q(-S)}{f_Q(P-S)}
\]
を$P$と$Q$のペアリングとします\footnote{この定義と証明は~\cite{alex}を参考にしました。
ただ本書で定義されているWeierstrassの$\sigma$関数は間違っているのでご注意ください。
正しくは
\[
\sigma(z)=z\prod_{\omega \in \Lambda \setminus 0}\left(1-\frac{z}{w}\right)\exp\left(\left(\frac{z}{w}\right)+\frac{1}{2}\left(\frac{z}{w}\right)^2\right).
\]
}。
\begin{theorem}
$e(P,Q)$は$f_P$, $f_Q$, $S$のとり方に依らずに定まり、$P$, $Q$に関して双線形写像となる。
\end{theorem}
特に$f_P$や$f_Q$を一番次数の大きい項の係数を1になるようにとる（これを正規化といいます）と、
$S \rightarrow O$とすると$f_Q(-S)/f_P(S) \rightarrow 1$となり、
\[
e(P,Q)=f_P(Q)/f_Q(P)
\]
と書けます。また、この式の対称性から$e(Q,P)=1/e(P,Q)$もわかります。

まず$f_P$のとり方に依存しないことを確認しましょう。
定理\ref{div_func}より与えられた$D_P$に対して$\Div(f)=D_P$となる$f$は定数倍の差しか違いません。
$f_P(Q+S)/f_P(S)$と比をとっている部分で定数倍は打ち消しあいます。
したがって$f_P$のとり方に依存しません。

次に$S$のとり方に依存しないことを確認します。
点$P$, $Q$と関数$f_P$, $f_Q$を固定して関数$F$を
\[
F(S):=e(P,Q)=\frac{f_P(Q+S)}{f_P(S)} \cdot \frac{f_Q(-S)}{f_Q(P-S)}
\]
と定義します。示したいことは$F(S)$が$S$に関して定数関数であることです。

そのために$F(S)$が零点も極も持たない関数であることを示します。
そうすれば定理\ref{div_func}より定数関数になるからです。

関数$f_P$は$\Div(f_P)=m(P)-m(O)$となるようにとりました。
$S$を動かすとき$f_P(Q+S)$は$f_P$を$Q$だけ平行移動したものです。
つまり$f_P(X)$が$X=P$で0となるなら$f_P(Q+S)$は$S=P-Q$で0になります。よって
\[
\Div(f_P(Q+S))=m(P-Q)-m(-Q).
\]
同様に$\Div(f_Q(-S))=m(-Q)-m(O)$, $\Div(f_Q(P-S))=m(P-Q)-m(P)$となります。
したがって
\begin{align*}
\Div(F)&=(m(P-Q)-m(-Q))-(m(P)-m(O))+(m(-Q)-m(O))\\
&-(m(P-Q)-m(P))=0
\end{align*}
となります。
$F$は零点も極も持たないので定数であることがわかりました。

次に双線形性を示しましょう。
点$P_1$, $P_2 \in E[m]$をとり$e(P_1+P_2,Q)=e(P_1,Q)e(P_2,Q)$を示せば十分です。
この示したい式を定義にしたがって展開すると
\begin{align*}
\frac{f_{P_1+P_2}(Q+S)}{f_{P_1+P_2}(S)} \frac{f_Q(-S)}{f_Q(P_1+P_2-S)}
&=
\frac{f_{P_1}(Q+S)}{f_{P_1}(S)} \frac{f_Q(-S)}{f_Q(P_1-S)}\\
& \cdot
\frac{f_{P_2}(Q+S)}{f_{P_2}(S)} \frac{f_Q(-S)}{f_Q(P_2-S)}.
\end{align*}
\[
f(X):=\frac{f_{P_1+P_2}(X)}{f_{P_1}(X)f_{P_2}(X)}
\]
とおいて式変形すると、
\begin{equation}\label{pairing_proof}
\frac{f(Q+S)}{f(S)}=\frac{f_Q(P_1+P_2-S)f_Q(-S)}{f_Q(P_1-S)f_Q(P_2-S)}.
\end{equation}
今から左辺が右辺に等しいことを示します。
まず、
\begin{align*}
\Div(f)
&=\Div(f_{P_1+P_2})-\Div(f_{P_1})-\Div(f_{P_2})\\
&=m(P_1+P_2)-m(O)-m(P_1)+m(O)-m(P_2)+m(O)\\
&=m((P_1+P_2)-(P_1)-(P_2)+(O)).
\end{align*}
因子$D:=(P_1+P_2)-(P_1)-(P_2)+(O)$は$\deg(D)=1-1-1+1=0$, $P_1+P_2-P_1-P_2+O=O$と
定理\ref{div_func}の条件を満たすのである関数$g$が存在して
\[
\Div(g)=D
\]
と書けます。すると
\[
\Div(f)=m\Div(g)=\Div(g^m)
\]
となり、$f$と$g^m$の因子が同じなので定数倍を除いて$f=g^m$と書けます。
すると、式（\ref{pairing_proof}）の左辺は
\begin{align*}
\frac{g^m(Q+S)}{g^m(S)}
 &=g(m(Q+S)-m(S))\\
 &\text{ここで$h(X):=f_Q(X-S)$とすると$\Div(h)=m(Q+S)-m(S)$より}\\
 &=g(\Div(h)) \quad \text{ここで定理\ref{weil_reciprocity}を使うと}\\
 &=h(\Div(g))\\
 &=h((P_1+P_2)-(P_1)-(P_2)+(O))=\frac{h(P_1+P_2)h(O)}{h(P_1)h(P_2)}.
\end{align*}
$h$の定義に戻るとこれは式（\ref{pairing_proof}）の右辺に等しく証明が終わりました。\qed

\section{Millerのアルゴリズム}
前節によりペアリングの定義はできました。
この節ではMiller（ミラー）のアルゴリズムと呼ばれる具体的なペアリングの計算方法を紹介します~\footnote{\url{http://crypto.stanford.edu/miller/}}。

楕円曲線$E$と自然数$m$に対して点$P \in E[m]$をとります。
ペアリングの計算に必要な$\Div(f_P)=m(P)-m(O)$となる関数$f_P$を構成しましょう。
いきなり構成するのは難しいので$m$が小さいところから作っていきます。
そのために関数$f^{(i)}_P$で
\[
\Div(f^{(i)}_P)=i(P)-(iP)-(i-1)(O)
\]
となるものを構成します。
記号が紛らわしいですが$i(P)$は因子$(P)$の$i$倍、$(iP)$は点$P$の$i$倍点からなる因子です。
$mP=O$なら、
\[
\Div(f^{(m)}_P)=m(P)-(mP)-(m-1)(O)=m(P)-(O)-(m-1)(O)=m(P)-m(O)
\]
となり$f^{(m)}_P$が求めたい関数$f_P$です。

小さい$i$から順に$f^{(i)}_P$を構成するために楕円曲線上の点の加算と直線の関係を見直します。
\image{miller-line.pdf}{点$P$と$Q$を通る直線および$P+Q$と$-(P+Q)$を通る直線}
\ref{sec:ec_add}節で紹介したように点$P=(x_1,y_1)$, $Q=(x_2,y_2)$を通る直線は
\[
y=\lambda (x-x_1)+y_1, \quad \text{ただし} \lambda:=\frac{y_2-y_1}{x_2-x_1}
\]
と書けました（$P=Q$のときは接線でした）。
$E$上の関数$l_{P,Q}$を
\[
l_{P,Q}(x,y):=y-(\lambda (x-x_1)+y_1)
\]
とします（関数$y$の係数は1に正規化しています）。
直線$l_{P,Q}(x,y)=0$は点$P$, $Q$, $-(P+Q)$で$E$と交わるので$l_{P,Q}$はそれらを零点に持ちます。
無限遠点では$y$の効果がでて位数3の極になります。
つまり
\[
\Div(l_{P,Q})=(P)+(Q)+(-P-Q)-3(O).
\]
同様に勝手な点$R=(x_R,y_R)$に対して関数$v_{R}$を
\[
v_R(x,y):=x-x_R
\]
とすると直線$v_R(x,y)=0$は点$R$, $-R$で交わり、無限遠点では位数2の極を持つので
\[
\Div(v_R)=(R)+(-R)-2(O).
\]
関数$l_{P,Q}$も関数$v_R$も点$P$, $Q$, $R$が与えられれば具体的に計算できます。
点$P$, $Q$に対して
\[
g_{P,Q}:=l_{P,Q}/v_{P+Q}
\]
とすると、
\begin{align*}
\Div(g_{P,Q}) &=\Div(l_{P,Q})-\Div(v_{P+Q})\\
&=(P)+(Q)+(-P-Q)-3(O)-(P+Q)-(-P-Q)+2(O)\\
&=(P)+(Q)-(P+Q)-(O).
\end{align*}
$i$, $j$を自然数として関数$f^{(i)}_P f^{(j)}_P g_{iP,jP}$を考えると
\begin{align*}
\Div(f^{(i)}_P f^{(j)}_P g_{iP,jP})
&=(i(P)-(iP)-(i-1)(O))+(j(P)-(jP)-(j-1)(O))\\
&+((iP)+(jP)-(iP+jP)-(O))\\
&=(i+j)(P)-((i+j)P)-(i+j-1)(O).
\end{align*}
これより
\[
f^{(i+j)}_P:=f^{(i)}_P f^{(j)}_P g_{iP,jP}
\]
とできます。この関係式を使うと小さい$i$から順に$f^{(i)}_P$を構成できます。

まず$\Div(f^{(1)}_P)=(P)-(P)-0(O)=0$ですから$f^{(1)}_P:=1$とします。
すると
\begin{align*}
f^{(2)}_P&=f^{(1)}_P f^{(1)}_P g_{P,P}=g_{P,P},\\
f^{(3)}_P&=f^{(1)}_P f^{(2)}_P g_{P,2P}=f^{(2)}_P g_{P,2P},\\
f^{(4)}_P&=f^{(2)}_P f^{(2)}_P g_{2P,2P}=\left(f^{(2)}_P\right)^2 g_{2P,2P}.\\
f^{(5)}_P&=f^{(1)}_P f^{(4)}_P g_{P,4P}:=f^{(4)}_P g_{P,4P}.
\end{align*}
このように小さい$i$から$2^iP$と$f^{(i)}_P$を順次求めることで$i=m$まで持っていけます。
2倍しながら求めるので\ref{binary-method}節の巾乗を求めるバイナリ法と同様の演算量$O(\log(m))$です。
この方法をMillerのアルゴリズムといいます。

アルゴリズムの擬似コードを書くとAlgorithm \ref{algo:miller}となります。
ここでは$f_P$を計算してから$Q$を代入するのではなく$Q$を代入しながら計算しています。

楕円曲線全般の定番のテキストは『The Arithmetic of Elliptic Curves』~\cite{silverman}です。
暗号への応用の観点から書かれた和書では『暗号理論と楕円曲線』~\cite{tsuji}や『代数学から学ぶ暗号理論』~\cite{miyaji}が詳しいです。
%なお、本書ではペアリングを関数の値を求める形で定義しましたが、別の形の定義もあります。
%\footnote{ペアリングの定義 : \url{http://homepage1.nifty.com/herumi/crypt/pairing-def.html}}

ペアリングを高速に計算することは新しい暗号方式にとって非常に重要です。
Tate（テイト）ペアリング~\cite{pairing-doukou}\index{Tateぺありんぐ@Tateペアリング}、optimal Ate（オプティマル エイト）ペアリングなど様々な方式が提案されています。
私は2014年の時点で世界最速な実装の一つをGitHubで公開しています~\footnote{\url{https://github.com/herumi/ate-pairing/}}。
実装方法については、またの機会に紹介しましょう。

\begin{algorithm}
\caption{Millerのアルゴリズム}
\label{algo:miller}
\begin{algorithmic}
\REQUIRE $P$, $Q \in E[m]$
\ENSURE $f=f_P(Q)$
\STATE $m$を2進数展開して$m=\sum_{i=0}^{s} b_i 2^i$（$b_i\in\Set{0,1}$, $b_s=1$）とする。
\STATE $f \leftarrow 1$, $T \leftarrow P$
\FOR {$i=s-1, s-2, \dots, 1, 0$}
\STATE $f \leftarrow f^2 \cdot g_{T,T}(Q), \quad T \leftarrow 2T$
\IF {$b_i = 1$}
\STATE{$f \leftarrow f \cdot g_{P,T}(Q), \quad T \leftarrow T+P$}
\ENDIF
\ENDFOR
\RETURN $f$
\end{algorithmic}
\end{algorithm}
\section{この章のまとめ}
楕円曲線上の点の有限形式和である因子を定義しました。
楕円曲線上の関数の零点と極の性質は因子を用いて記述できます。
ペアリングはある因子から定まる楕円曲線上の関数を用いて定義されます。
ペアリングはMillerアルゴリズムを用いると比較的高速に計算でき、様々な高速化手法が提案されています。

近年、ペアリングを使った暗号の標準化が進んでいます。
パラメータが整備され、使いやすいライブラリが出てくれば少しずつ実験やアプリケーションも作りやすくなるでしょう。
本書で紹介しきれなかった応用例も数多くあります。
これからの普及が望まれます。