数理解析研究所講究録
第 1874 巻 2014 年 32-44

32

暗号から数論ヘ-代数曲線に関するいく
つかのアルゴリズム

From cryptography to number theorysome algorithms on algebraic curves首都大学東京・大学院理工学研究科・数理情報科学専攻

内山成憲，内田幸寛

Shigenori UCHIYAMA, Yukihiro UCHIDA
Department of Mathematics and Information Sciences
Graduate School of Science and Engineering
Tokyo Metropolitan University
uchiyama-shigenori@tmu.ac.jp, yuchida@tmu.ac.jp

1

はじめに

暗号と数論との明示的な関係は，1970 年代に提案され現在世界中で最も広く使用されている公開鍵暗号方式である RSA 暗号の提案まで遡ることが出来る．RSA 暗号は十分大きなサイズの合成数の素因数分解問題の計算量的な困難さにその安全性の根拠をおいているが，その後，素因数分解問題と同様の計算量的困難さを持つと期待される有限体上の離散対数問題等，いくつかの数論的な問題の困難さに基づく実用的な暗号方式が提案されてきた．このように，この 30 年程の間，暗号理論は数論，特に計算数論と密接な関係を保ちながら発展してきたとも言えよう．特に特筆すべきは代数曲線に関するアルゴリズム研究の発展である．これは，$19S0$ 年代に Koblitz と Miller により独立に提案された楕円曲線暗号の提案により明示的になったと言えよう．ここでは，楕円曲線暗号の安全性評価研究の際に利用されたことで注目され，その後 $ID$ ベース暗号に代表されるペアリング暗号と呼ばれる一連の暗号方式の研究へとつながった33
代数曲線上のペアリングに関連するいくつかのアルゴリズムについて述
べる．

代数曲線上には Weil ペアリングをはじめ，様々なペアリングが定義されているが，計算速度等の観点から，Tate-Lichtenbaum ペアリング (単に Tate ペアリングとも呼ぶ) やその変種がよく用いられている．このペアリングは，まず Tate [14] によって，Abel 多様体上のペアリングとして定義された．Lichtenbaum [6] は，Abel 多様体がある代数曲線の Jacobi 多様体である場合に，Tate の定義したペアリングを曲線の言葉で書き表し$bey$-R\"uck [4] は，彼らの結果を有限体上定義された代数曲線に対した．
て適用し，Jacobi 多様体上の離散対数問題に応用した．
Tate-Lichtenbaum ペアリングの計算には，Miller のアルゴリズムがよく用いられてきた (cf. [4, 7, 8]). 2007 年，Stange [11] は楕円曲線の Tate
ペアリングを計算する新しいアルゴリズムを提案した．このアルゴリズ
ムでは，elliptic divisibility sequence (EDS) の一般化として Stange によって定義された，elliptic net が用いられる．
本稿では，elliptic net を超楕円曲線に一般化して hyperelliptic net を定義し，これを用いて超楕円曲線上の Tate-Lichtenbaum ペアリングを書き表す公式を与える．また，種数 2 の超楕円曲線に対して，hyperelliptic
net が満たす漸化式に基づく Tate-Lichtenbaum ペアリングの計算アルゴ
リズムを述べる．本稿の内容は [15] に基づく．証明は省略したので，[15]を参照していただきたい．

2

Elliptic net
本節では Stange の定義した elliptic net について述べる．詳細について

は，[11, 12] を参照していただきたい．Elliptic net は $EDS$ を一般化したものであるので，まず EDS について述べる．
定義 1 (M. Ward [16]). 整数列
quence (EDS) であるとは，$\{h_{n}\}_{n\geq 0}$が，elliptic divisibility se-$h_{m+n}h_{m-n}=h_{m+1}h_{m-1}h_{n}^{2}-h_{n+1}h_{n-1}h_{m}^{2}$

がすべての $m\geq n\geq 1$ に対して成り立ち， が $m$ を割り切るならば妬
$n$が$h_{m}$

を割り切ることをいう．

34
Ward 1 よ，(適当な条件を満たす) EDS が楕円曲線とその上の 1 点の組と対応することを証明した (cf. [16, Theorem 12.1]).
Stange は，EDS を一般化して，elliptic net を次のように定義した．
$R$
定義 2 (Stange [11]). $A$ を有限生成自由 Abel 群，
を整域とする．写像$r,$ $s\in A$ に対して
$W:Aarrow R$ が elliptic net であるとは，すべての $p,$$q,$

次の式が成り立つことをいう．

$W(p+q+s)W(p-q)W(r+s)W(r)$$+W(q+r+s)W(q-r)W(p+s)W(p)$$+W(r+p+s)W(r-p)W(q+s)W(q)=0.$
前に定義した EDS$\{h_{n}\}_{n\geq 0}$上の数列に拡張すは elliptic net になることが確かめられる．

を $h_{-n}=-h_{n}$ によって$\mathbb{Z}$ると，写像EDS と同様に，elliptic net も楕円曲線と対応する．その対応を述べるをために，楕円曲線 , 自然数に対し， 上の有理関数$W:\mathbb{Z}arrow \mathbb{Z};n\mapsto h_{n}$

$E$

$n,$

$E^{n}$$v\in \mathbb{Z}^{n}$$\Psi_{v}$構成する．

まず， が複素数体上定義されている場合を考える．このとき， 内の格子 A と同型が存在する．格子 A に対応する Weierstrass$E$$\mathbb{C}$$E(\mathbb{C})\cong \mathbb{C}/\Lambda$の$\sigma$関数を$\sigma(u)=u\prod_{\omega\in\Lambda\backslash \{0\}}(1-\frac{u}{\omega})\exp(\frac{u}{\omega}+\frac{u^{2}}{2\omega^{2}})$で定義する．

$v=(v_{1}, \ldots,v_{n})\in \mathbb{Z}^{n}$に対し， 上の有理型関数$\mathbb{C}^{n}$$\Psi_{v}$を$\Psi_{v}(u_{1}, \ldots, u_{n})=\frac{\sigma(v_{1}u_{1}+\cdots+v_{n}u_{n})}{\prod_{i=1}^{n}\sigma(u_{i})^{2v^{2}-\Sigma_{j=1}^{n}v_{i}v_{j}}\prod_{1\leq i<j\leq n}\sigma(u_{i}+u_{j})^{v_{i}v_{j}}}$で定義する． は各変数に対して A を周期に持つので， をが関数とみなすことができる．そこで，$\Psi_{v}$$\Psi_{v}$$P_{1},$に対応するとき，$\ldots,P_{n}\in E(\mathbb{C})$$E^{n}$$u_{1},$

上の有理$\ldots,u_{n}\in \mathbb{C}$と定める．
とは限らない) 一般の体 $K$ 上で定義されている$\Psi_{v}(P_{1}, \ldots, P_{n})=\Psi_{v}(u_{1}, \ldots,u_{n})$楕円曲線 $E$ が (標数場合も， 上の有理関数$0$$E^{n}$$P_{1},$$\ldots,$$P_{n}\in E(K)$を用いて，写像$\Psi_{v}$で同様の性質を持つものが定義できる．

$P=(P_{1}, \ldots, P_{n})$として，とおく．今定義した$W_{P}:\mathbb{Z}^{n}arrow K$

を$W_{P}(v)=\Psi_{v}(P)$で定義する．

$\Psi_{v}$

35
定理

$3$

(Stange [11, Theorem 4]).

$W_{P}$

は elliptic net である．

という．逆に，elliptic net$W$ がある条件を満たせば，$K$ 上定義さが与えられたとき，れた楕円曲線 $E$ と 点君，$W=W_{P}$ となる．
．
．
，Pn $\in E$ (K) が存在して，ことが示される (cf. [12, Theorem 6.7]).
この $W_{P}$ を $E$ と $P$ に対応する elliptic net$W:\mathbb{Z}^{n}arrow K$$n$3

楕円曲線上の Tate ペアリング
本節では，Stange [11] で与えられた，楕円曲線上の Tate ペアリングを

elliptic net によって表す公式について述べる．
$\mathbb{F}_{q}$を$q$個の元を持つ有限体， をその代数閉包とする． を$E$$\overline{\mathbb{F}}_{q}$

義された楕円曲線として， の加法の単位元を
$E$

$O$

$\mathbb{F}_{q}$上定で表す． を $q-1$ の$m$$E(\mathbb{F}_{q})[m]=\{P\in E(\mathbb{F}_{q})|[m]P=O\}$ とする．
正の約数，
$E$

上の Tate ペアリングは，写像$\tau_{m}:E(\mathbb{F}_{q})[m]\cross E(\mathbb{F}_{q})/mE(\mathbb{F}_{q})arrow \mathbb{F}_{q}^{\cross}/(\mathbb{F}_{q}^{\cross})^{m}$であり，次のように定義される．

$P\in E(\mathbb{F}_{q})[m]$$[m]P=O$ だかとする．

$div(f_{P})=m(P)-m(O)$ となる， 上定義された 上の有理関数
ら，が存在する．
に対し，線形同値 $(Q)-(O) \sim\sum_{i=1}^{r}n_{i}(Q_{i})$ が成り立つようなを選ぶ．こ$\mathbb{F}_{q}$$E$$f_{P}$$Q\in E(\mathbb{F}_{q})$$n_{1},$$\ldots,$

こで，右辺の因子は$n_{r}\in \mathbb{Z},$$Q_{1},$$\ldots,$$\mathbb{F}_{q}$$Q_{r}\in E(\overline{\mathbb{F}}_{q})(Q_{i}\neq P, O)$

上定義されているようにする．このとき，$\tau_{m}(P, Q)=\prod_{i=1}^{r}f_{P}(Q_{i})^{n_{i}}mod (\mathbb{F}_{q}^{\cross})^{m}$$(左辺は正確には \tau_{m}(P, Qmod mE(\mathbb{F}_{q}))$ であるが，省略してと定義する．

と表す．以下でも同様の省略を行う．)
Stange は，elliptic net を用いて Tate ペアリングを表示する公式を与$\tau_{m}(P, Q)$

えた．

定理 4 (Stange [11, Corollary 1]). $P\in E(\mathbb{F}_{q})[m],$ $Q\in E(\mathbb{F}_{q}),$ $P,$ $Q,$ $P+$
$Q\neq O$とする．このとき次の式が成り立つ．
$\tau_{m}(P, Q)=\frac{W_{P,Q}(m+1,1)W_{P,Q}(1,0)}{W_{P,Q}(m+1,0)W_{P,Q}(1,1)}mod (\mathbb{F}_{q}^{\cross})^{m}$

また，Stange は，この公式を用いて Tate ペアリングを計算するアルゴ
リズムを与えた．

以下では，Stange の結果を超楕円曲線に拡張する．

36

Hyperelliptic net

4

本節では hyperelliptic net を定義し，その性質について述べる．詳細については，[15, \S \S 3-4] を参照していただきたい．Elliptic net は漸化式で定義されたが，hyperelliptic net については，先に超楕円曲線をもとに写像を定義し，それが満たす漸化式を証明する．
$C$

を方程式
$y^{2}+(b_{g}x^{g}+\cdots+b_{0})y=x^{2g+1}+a_{2g}x^{2g}+\cdots+a_{0}$で定まる体 $K$ 上定義された種数
で表す．
無限遠点を

$g$

の超楕円曲線とする． のただ 1 つの$C$$\infty$$J$ はを $C$ の Jacobi 多様体とする．

$J$上定義された次数

$K$

$0$

$g$

$C$ の
次元 Abel 多様体である．

の因子類全体がなす群を Pic (C) とすれば，群同$J$ のテータ因子型 $\lambda:Pic^{0}(C)arrow J(K)$ が存在する．

$\Theta$を$\Theta=\{\lambda(\sum_{i=1}^{g-1}(P_{i})-(g-1)(\infty))P_{1}, \ldots, P_{g-1}\in C\}$で定める．

楕円曲線の場合と同様に，まず複素数体上で考える．超楕円曲線上定義されているとする．このとき， 内の格子 A と，同型$C$が$\mathbb{C}$$J(\mathbb{C})\cong \mathbb{C}^{g}/\Lambda$$\mathbb{C}^{g}$が存在する．

Weierstrass の$\sigma$関数の一般化として，超楕円$\sigma$関数$\sigma:\mathbb{C}^{g}arrow \mathbb{C}$が定義$\sigma(u)=0$ となるのは $umod \Lambda$ がされている． は整関数である．また，$\sigma$上の点に対応するときであり，そのときに限る．超楕円関数の定義やより詳しい性質については，[2,9] やその中で挙げられていテータ因子$\Theta$$\sigma$

る文献を参照していただきたい．
$n$$\Phi_{v}$を自然数とし，$v=(v_{1}, \ldots,v_{n})\in \mathbb{Z}^{n}$とする．

$(\mathbb{C}^{g})^{n}$上の有理型関数を次の式で定義する．
$\Phi_{v}(u^{(1)}, \ldots, u^{(n)})=\frac{\sigma(v_{1}u^{(1)}+\cdots+v_{n}u^{(n)})}{\prod_{i=1}^{n}\sigma(u^{(i)})^{2v^{2}-\Sigma_{j=1}^{n}viv}j\prod_{1\leq i<j\leq n}\sigma(u^{(i)}+u^{(j)})^{v_{i}v_{j}}}.$

関数の擬周期性から， は各変数について A を周期に持つ．
よって， を 上の有理関数とみなすことができる．
超楕円$\Phi_{v}$が$\Phi_{v}$$\sigma$$u^{(n)}\in \mathbb{C}^{g}$$u^{(1)},$$\ldots,$$P_{1},$$J^{n}$に対応するとき，と定める．
$\Phi_{v}$が満たす性質をいくつか述べる．

$\ldots,$$P_{n}\in J(\mathbb{C})$$\Phi_{v}(P_{1}, \ldots, P_{n})=\Phi_{v}(u_{1}, \ldots, u_{n})$37
命題 5. 任意の$v\in \mathbb{Z}^{n}$に対し，$\Phi_{-v}=\{\begin{array}{ll}-\Phi_{v} (g\equiv 1,2 (mod 4)) ,\Phi_{v} (g\equiv 0,3 (mod 4)) .\end{array}$$e_{1},$$\ldots,$

命題 6.

$e_{n}$

を$v\in \mathbb{Z}^{n}$$\mathbb{Z}^{n}$の標準基底とする．

とする．

1. 恒等的に $\Phi_{v}=0$ であるための必要十分条件は $v=0$ である．
$\Phi_{v}=1.$
2. $v=e_{i}$ または $v=e_{i}+e_{j}(i\neq j)$ ならば，

$P=(P_{1}, \ldots, P_{n})\in J^{n},$命題 7. $m$ を自然数とし，
$T=$
とする．
を整数成分の $n\cross m$ 行列とする．このとき次の式が成り立つ．
$v\in \mathbb{Z}^{m}$$(t_{ij})$$\Phi_{v}(PT)=\frac{\Phi_{Tv}(P)}{\prod_{i=1}^{m}\Phi_{Te_{i}}(P)^{2v_{i}^{2}-\Sigma_{j=1}^{m}viv_{j}}\prod_{1\leq i<j\leq m}\Phi_{T(e_{i}+e_{j})(P)^{v_{i}v}j}},$$PT=([t_{11}]P_{1}+\cdots+[t_{n1}]P_{n}, \ldots, [t_{1m}]P_{1}+\cdots+[t_{nm}]P_{n})$ とする．
ここで，上の有理関数定義から，$J\cross J$$\mathcal{F}_{g}$を $\mathcal{F}_{g}(P, Q)=\Phi_{(1,-1)}(P, Q)$ で定義する． の$\Phi_{v}$$\Phi_{(1,-1)}(u, v)=\frac{\sigma(u+v)\sigma(u-v)}{\sigma(u)^{2}\sigma(v)^{2}}$であり，これを Weierstrass の 関数の拡張を用いて書き表す公式が知られている (cf. [3]). 命題 7 から次の命題が従う．
$\wp$

命題 8. $P=(P_{1}, \ldots, P_{n})\in J^{n},$ $v,$
ならば，次の式が成り立つ．

$w\in \mathbb{Z}^{n}$とする． $w,$ $v+w,$ $v-w\neq 0$$v,$$\frac{\Phi_{v+w}(P)\Phi_{v-w}(P)}{\Phi_{v}(P)^{2}\Phi_{w}(P)^{2}}=\mathcal{F}_{g}([v_{1}]P_{1}+\cdots+[v_{n}]P_{n}, [w_{1}]P_{1}+\cdots+[w_{n}]P_{n})$$\Phi_{v}$.

に関する漸化式は次のように与えられる．

$1\leq i\leq m$ に対して $v^{(i)}\in((1/2)\mathbb{Z})^{n}$ である
定理 9. $m>2^{g}$ を整数とし，とする．すべての $1\leq i,j\leq m$ に対して$v^{(i)}+v^{(j)},v^{(i)}-v^{(j)}\in \mathbb{Z}^{n}$であ$m$ 次正方行列 $A$ をると仮定する．

$A=(\Phi_{v^{(i)}+v^{(j)}}\Phi_{v^{(i)}-v^{(j)}})_{1\leq i,j\leq m}$$\det A=0$ である．特に，(mod4) かつで定義する．このとき，が偶数ならば， は交代行列であり，pf $A=0$ である．ただし，pf$g\equiv 1,2$

$m$

$A$

は $A$ の Pfaffian である．

$A$

38
ここまで複素数体上で考えていたが，楕円曲線の場合と同様に任意の$K$ 上で定義された超楕円曲線に
体 $K$ 上で考えることができる．実際，
$C$ の
が定義さ
対して，
Jacobi 多様体を とすると， 上の有理関数
$C$

$J$

$J^{n}$$\Phi_{v}$

れて，ここまで述べた性質を満たしている．
超楕円曲線に対応する hyperelliptic net は次のように定義される．
定義 10.

$P_{1},$$\ldots,$$P_{n}\in J(K)$とする．すべての $1\leq i\leq n$ に対して

であり，すべての $1\leq i<j\leq n$ に対して
このとき，写像$W_{P_{1},\ldots,P_{n}}:\mathbb{Z}^{n}arrow K$$P_{i}+P_{j}\not\in\Theta$$P_{i}\not\in\Theta$

であると仮定する．

を$W_{P_{1},\ldots,P_{n}}(v)=\Phi_{v}(P_{1}, \ldots, P_{n})$

$C,$
で定義し，

5

$P_{1}$, . . , 疏に対応する hyperelliptic net と呼ぶ．

Tate-Lichtenbaum ペアリング
本節では，hyperelliptic net を用いて超楕円曲線上の Tate-Lichtenbaum

ペアリングを書き表せることを示す．
$C$ を
まず Tate-Lichtenbaum ペアリングについて述べる．

上定義された既約非特異射影代数曲線とし，少なくとも 1 つ 有理点を持つとす$C$ の上定義された次数 の因子類全体がなす群を $Pic^{0}(C)$ とする．
る．
$m$ を $q-1$ の正の約数とする．
$C$ 上のTate-Lichtenbaum ペアリング$\mathbb{F}_{q}$$\mathbb{F}_{q}$$0$$\mathbb{F}_{q}$$\tau_{m}$:$Pic^{0}(C)[m]\cross Pic^{0}(C)/mPic^{0}(C)arrow \mathbb{F}_{q}^{\cross}/(\mathbb{F}_{q}^{\cross})^{m}$を次のように定義する．

$\overline{D}\in Pic^{0}(C)[m],$ $\overline{E}\in Pic^{0}(C)$とする．

$D,$ $E$

をそ$D$ と $E$ は共通の点を持たないと仮定する．
の代表元として，$mD\sim 0$ となるから， 上定義された $C$ 上の有理関数
で $div(f_{D})=mD$

れぞれ $D,$$\overline{E}$$f_{D}$$\mathbb{F}_{q}$となるものが存在する．

$E= \sum_{i=1}^{r}n_{i}(Q_{i}),$$n_{i}\in \mathbb{Z},$$Q_{i}\in C(\overline{\mathbb{F}}_{q})$として，$\tau_{m}(\overline{D},\overline{E})=\prod_{i=1}^{r}f_{D}(Q_{i})^{n_{i}}mod (\mathbb{F}_{q}^{\cross})^{m}$と定義する．

Tate-Lichtenbaum ペアリング は，双線形かつ非退化である．FreyR\"uck [4] による非退化性の証明は，Tate [14] と Lichtenbaum [6] の結果に基づくものである．より直接的な証明が，[1,5,10] で与えられている．
$\tau_{m}$

39
$J$

$\tau_{m}$を $C$ の Jacobi 多様体とする．群同型 $\lambda:Pic^{0}(C)arrow J(\mathbb{F}_{q})$ によってを双線形写像$J(\mathbb{F}_{q})[m]\cross J(\mathbb{F}_{q})/mJ(\mathbb{F}_{q})arrow \mathbb{F}_{q}^{\cross}/(\mathbb{F}_{q}^{\cross})^{m}$と見なすことができる．

以下， 上定義された種数 の超楕円曲線$\mathbb{F}_{q}$$g$$C:y^{2}+(b_{g}x^{9}+\cdots+b_{0})y=x^{2g+1}+a_{2g}x^{2g}+\cdots+a_{0}$を考える．これはただ 1 つの無限遠点$\infty\in C(\mathbb{F}_{q})$を持つ．楕円曲線の場

合と同様に，hyperelliptic net を用いて Tate-Lichtenbaum ペアリングは
次のように表される．
定理 11. $P\in J(\mathbb{F}_{q})[m],$$Q\in J(\mathbb{F}_{q}),$$P,$ $Q,$ $P+Q\not\in\Theta$

であると仮定する．

このとき，$\tau_{m}(P, Q)=\frac{W_{P,Q}(m+1,1)W_{P,Q}(1,0)}{W_{P,Q}(m+1,0)W_{P,Q}(1,1)}mod (\mathbb{F}_{q}^{\cross})^{m}$

6

ペアリングの計算アルゴリズム

Stange は elliptic net を高速に計算するアルゴリズムを考案し，楕円曲
線上の Tate ペアリングが $O(\log m)$ 回の四則演算で計算できることを示した．種数 2 の超楕円曲線についてもこのアルゴリズムを拡張して，TateLichtenbaum ペアリングを $O(\log m)$ 回の四則演算で計算できることを以下に示す．
$g=2$ であるとする．すなわち，次のよ以下，前節と同じ記号を用い，

うな超楕円曲線を考える．
$C:y^{2}+(b_{2}x^{2}+b_{1}x+b_{0})y=x^{5}+a_{4}x^{4}+\cdots+a_{0}.$$W_{P,Q}(m, n)$ を $W(m, n)$ と表す．
簡単のため，$W(m, 0),$ $W(m, 1)$ を計算するアルゴリズムを構成す
定理 11 によれば，れば十分である．そのようなアルゴリズムは Stange が与えたアルゴリズ

ムを拡張して得られる．
整数 に対し， を中心とするブロック $V$ を
$k$

$k$

$V=[[W(k-7,0), W(k-6,0), \ldots, W(k+8,0)],$$[W(k-3,1), W(k-2,1), \ldots, W(k+3,1)]]$で定義する．このブロック $V$ を引数とする，次の二つの関数を定義する．

40
1. Double(V): $2k$ を中心とするブロックを返す．
2. DoubleAdd(V): $2k+1$ を中心とするブロックを返す．
これらの関数で返されるブロックは，hyperelliptic net が満たす漸化式 (定理 9) を用いて計算される．これについてより詳しく述べる．
$g=2,$ $m=6$ とすると，行列定理 9 において，$A=(W(v^{(i)}+v^{(j)})W(v^{(i)}-v^{(j)}))_{1\leq i,j\leq 6}$$v^{(i)}=(m_{i},n_{i})$$pfA=0$ が成り立つ．
に対して，とおいて，Pfaffian の展

開公式を用いると，$\sum_{i=2}^{6}(-1)^{i}$

pf $A^{1,i}\cdot W(m_{1}+m_{i},n_{1}+n_{i})W(m_{1}-m_{i},n_{1}-n_{i})=0$となる．ここで， は の第 1 行，第 行，第 1 列，第 列を取り除いの値を表 1 のよて得られる 4 次正方行列である．この式において，うに定めることで，Double(V), DoubleAdd(V) を計算する漸化式が得ら$-3\leq J\leq 4$ とする．
れる．ただし，$A^{1,i}$

$A$

$i$

$i$

$m_{i},$

表 1:$m_{i}$と$n_{i}$$n_{i}$の値$W(m_{1}-m_{2}, n_{1}-n_{2})pfA^{1,2}$ による除算が必要で漸化式の計算の際に，ある．しかし，これらはに依存しないので，逆数をあらかじめ計算
$j,$

$k$

$pfA^{1,2}$ はしておけば，除算を避けることができる．

る値なので，$\triangle(P)$$\Delta(P)=$$P$

のみによって定まと表すことにする．すなわち，

pf $A^{1,2}=W(5,0)-W(4,0)W(2,0)^{3}+W(3,0)^{3}$$W(m, 0)$ と $W(m, 1)$ を求めるアルゴリズムは Algorithm 1以上から，のように書ける．

41
Algorithm 1 Hyperelliptic Net Algorithm
Input: Hyperelliptic net の初期値 $W(i, 0)(-6\leq i\leq 9),$ $W(i, 1)(-4\leq$$i\leq 4)$と整数 $m.$$m$の 2 進展開を $m=(d_{k}d_{k-1}\ldots d_{1})_{2}(d_{k}=1)$ とする．

Output: $W(m, 0),$ $W(m, 1)$
1: $Varrow[[W(-6,0), W(-5,0), \ldots, W(9,0)],$$[W(-2,1), W(-1,1), \ldots, W(4,1)]]$

2: for $i=k-1$ down to 1 do

3:

4:
5:
6:
7:

Othen
$Varrow$ Double(V)else
if$d_{i}=$$Varrow$

DoubleAdd(V)end if
8: end for
9: return $V[0,7],$ $V[1,3]//W(m, 0),$ $W(m, 1)$
Algorithm 1 では初期値 $W(i, 0)(-6\leq i\leq 9),$ $W(i, 1)(-4\leq i\leq 4)$ の計算をあらかじめしておく必要がある．この初期値は次のように計算され$P,$の Mumford 表現をそれぞれ $(t^{2}+u_{11}t+u_{12}, v_{11}t+v_{12})$ ,る．
$Q\in J(\mathbb{F}_{q})$$(t^{2}+u_{21}t+u_{22}, v_{21}t+v_{22})$$(x_{2}, y_{2})-2(\infty)$とする．言い換えれば，点$P$が因子 $(x_{1}, y_{1})+$に対応するとき，$u_{11}=-(x_{1}+x_{2}) , u_{12}=x_{1}x_{2},$$v_{11}= \frac{y_{1}-y_{2}}{x_{1}-x_{2}}, v_{12}=\frac{x_{1}y_{2}-x_{2}y_{1}}{x_{1}-x_{2}}$

である．点

$Q$

$W(0,0),$ $W(1,0),$ $W(0,1)$ ,についても同様である．まず，$W(1,1),$ $W(2,0)$ の値を次の式で計算する．

$W(0,0)=0, W(1,0)=W(0,1)=W(1,1)=1,$$W(2,0)=(-4u_{12}+6u_{11^{2}}+(-b_{2}^{2}-4a_{4})u_{11}+b_{1}b_{2}+2a_{3})v_{12}+2v_{11^{3}}$$+(3b_{1}-3b_{2}u_{11})v_{11^{2}}+((-8u_{11}+b_{2}^{2}+4a_{4})u_{12}+2u_{11^{3}}$$+(b_{2}^{2}-2a_{4})u_{11^{2}}+(2a_{3}-2b_{1}b_{2})u_{11}-b_{0}b_{2}+b_{1}^{2}-2a_{2})v_{11}$$+2b_{2}u_{12^{2}}+(b_{2}u_{11^{2}}-4b_{1}u_{11}-a_{3}b_{2}+2a_{4}b_{1}-2b_{0})u_{12}$$-b_{2}u_{11^{4}}+(a_{4}b_{2}+b_{1})u_{11^{3}}+(-a_{3}b_{2}-a_{4}b_{1}+3b_{0})u_{11^{2}}$$+(a_{2}b_{2}+a_{3}b_{1}-2a_{4}b_{0})u_{11}-a_{2}b_{1}+a_{3}b_{0}.$42
他の項は，直接計算するには式が巨大すぎるので，命題 8 から得られる
次の公式を用いる．

(1)$\frac{W(m+1,i)W(m-1,i)}{W(m,i)^{2}}=\mathcal{F}_{2}([m]P+[i]Q, P)$$i=0,1$ であり，
ここで，$\mathcal{F}_{2}(P,Q)$

は次の式で計算される．

$\mathcal{F}_{2}(P, Q)=-(v_{11}^{2}-b_{2}u_{11}v_{11}+b_{1}v_{11}-u_{11}u_{12}+u_{11}^{3}-a_{4}u_{11}^{2}+a_{3}u_{11})$$+(v_{21}^{2}-b_{2}u_{21}v_{21}+b_{1}v_{21}-u_{21}u_{22}+u_{21}^{3}-a_{4}u_{21}^{2}+a_{3}u_{21})-u_{12}u_{21}+u_{11}u_{22}.$式 (1) で $W(m+1,i)$ を計算する際に $W(m-1,i)$ による除算が必要であることに注意しなければならない．

以上のアルゴリズムによって，次の定理が得られる．
定理 12. 次の値がすべて$W(2,0),$ $W(3,0),$$\ldots,$$O$

でないと仮定する．

$W(8,0)$ ,$W(-4,1), W(-3,1), \ldots, W(3,1), \triangle(P)$ .

$W(m, 0)$ と $W(m, 1)$ はこのとき，$\mathbb{F}_{q}$(2)における $O(\log m)$ 回の四則演算で計算できる．

定理 11 を用いると，次の系を得る．
系 13. (2) の値がすべて$0$でないならば，$\tau_{m}(P,Q)$は$\mathbb{F}_{q}$における $0(\log m)$

回の四則演算で計算できる．
注意 14. Miller のアルゴリズムを用いた場合も，$\tau_{m}(P, Q)$ を$\mathbb{F}_{q}$における$O(\log m)$ 回の四則演算で計算できる．

本節で述べたアルゴリズムは，次のような特徴を持つ．
$\bullet$$\mathbb{F}_{q}$における除算をほとんど必要としない．より正確に言えば，除算

回数は $m$ に依存しない．
$\bullet$Miller のアルゴリズムとは異なり，計算時間が $m$ の Hamming 重み(2 進展開における 1 の個数) にほとんど依存しない．

$\bullet$$\mathbb{F}_{q}$の拡大体における計算を必要としない．

43

7

まとめ

本稿では，Stange によって定義された elliptic net を超楕円曲線に拡張し，
hyperelliptic net を定義した．また，hyperelliptic net が満たす漸化式を導いた．次に，超楕円曲線上の Tate-Lichtenbaum ペアリングを hyperelliptic
net で表す公式を述べた．最後に，hyperelliptic net を用いて種数 2 の超楕円曲線上の Tate-Lichtenbaum ペアリングを計算するアルゴリズムを与えた．

Hyperelliptic net を用いたアルゴリズムの実装については，田中覚氏(首都大学東京) との共同研究 [13] により行われている．この結果によれ
ば，実用的な曲線について実装評価は得られたものの，Miller のアルゴリズムと比較してまだ改善の余地がかなりあると考えられる．Elliptic netの計算で行われているような，演算量の削減による高速化が今後の課題
である．

参考文献
[1] P. Bruin, ”The Tate pairing for Abelian varieties over finite fields,”
J. Th\’eor. Nombres Bordeaux 23 (2011) 323-328.

[2] V. M. Buchstaber, V. Z. Enolskii, D. V. Leykin, “Kleinian functions,
hyperelliptic Jacobians and applications,” Rev. Math. Math. Phys.
10 (1997) 1-125.
[3] V. M. Buchstaber, V. Z. Enolskii, D. V. Leykin, “A recursive familyof differential polynomials generated by the Sylvester identity andaddition theorems for hyperelliptic Kleinian fUnctions,” Funct. Anal.
Appl. 31 (1997) 240-251.
, H.-G. R\"uck, “A remark concerning $m$-divisibility and the[4] $G.$
discrete logarithm in the divisor class group of curves,” Math. Comp.
62 (1994) 865-874.
$\mathbb{R}ey$[5] F. Hess, “A note on the Tate pairing of curves over finite fields,”
Arch. Math. (Basel) 82 (2004), 28-32.

[6] S. Lichtenbaum, “Duality theorems for curves over -adic fields,”
Invent. Math. 7 (1969) 120-136.

44[7] V. S. Miller, “Short programs for functions on curves,” unpublishedmanuscript (1986), http: //crypto. stanford. $edu/miller/.$[8] V. S. Miller, “The Weil pairing, and its efficient calculation,”
Cryptology 17 (2004) 235-261.

$J.$[9] 大西良博，“超楕円函数論，“ 第 15 回整数論サマースクール報告集 (2008) 131-176, http: $//www$ . ccn. yamanashi. ac. $jp/-yonishi/$/research/pub/ss2007/06onishi. pdf.

[10] E. F. Schaefer, “A new proof for the non-degeneracy of the Frey-R\"uckpairing and a connection to isogenies over the base field,” Computational aspects of algebmic curves, 1-12, Lecture Notes Ser. Comput.
13, World Sci. Publ., Hackensack, $NJ$ , 2005.

[11] K. E. Stange, “The Tate pairing via elliptic nets,” Pairing-Based$Cryptography-$ Pairing 2007, 329-348, Lecture Notes in Comput.
Sci., 4575, Springer, Berlin, 2007.

[12] K. E. Stange, “Elliptic nets and elliptic curves,” Algebra Number
Theory 5 (2011) 197-229.
[13] 田中覚，内田幸寛，内山成憲，“Hyperelliptic Net を用いた TateLichtenbaum Pairing の実装について，” 日本応用数理学会 2012 年
度講演予稿集 (2012) 19-20.
[14] J. Tate, “ $WC$-groups over -adic fields,” S\’eminaire Bourbaki, $exp.$
no. 156 (1957).
$\mathfrak{p}$[15] Y. Uchida, S. Uchiyama, “The Tate-Lichtenbaum pairing on a hyperelliptic curve via hyperelliptic nets,” Pairing-Based Cryptography–
Pairing 2012, 218-233, Lecture Notes in Comput. Sci., 7708,
Springer, Berlin, 2013.

[16] M. Ward, “Memoir on elliptic divisibility sequences,” Amer. J. Math.
70 (1948) 31-74.