射影座標を用いた場合のMiller Algorithmについてのメモ

楕円曲線

Miller Algorithmの実装を高速化した際のメモ。

Miller Algorithmは基本紹介される際にはEuclid空間上の楕円曲線の点について紹介されるが、変数変換をしてやることで射影座標上のアルゴリズムとすることが出来る。(なお、Miller Algorithm自体は任意の種数の代数曲線について適用が可能。詳しくは元論文。)

以降、$E/K$ を標数が2でない体 $K$ 上の楕円曲線とし、 $E[m]$ を $E$ の $ m $ ねじれ点の集合とする。また、$x(P)$, $y(P)$, $z(P)$はそれぞれ点 $P$ の $x, y, z$ 座標を表すこととし、$E$はWeierstrass標準形 $y ^ 2 = x ^ 3 + ax + b$ と表せるとする。

line_coeff関数

入力: $ P, Q \in E$

$$ \mathrm{line\_coeff}(P, Q) = \begin{cases} \frac{3x(P) ^ 2+az(P) ^ 2}{2y(P)z(P)} & x(P)z(Q) = z(P)x(Q) \newline \frac{y(Q)z(P) - y(P)z(Q)}{x(Q)z(P) - x(P)z(Q)} & other \end{cases} $$

h関数

入力: $ P, Q, R \in E[m] $

if (P == Q and y(P) == 0) or (P != Q and x(P) * z(Q) = x(Q) * z(P)) {
  return (x(R) * z(P) - x(P) * z(R)) / (z(P) * z(R))
}

l = line_coeff(P, Q)
p = z(Q) * (y(R) * z(P) - y(P) * z(R) - l * (x(R) * z(P) - x(P) * z(R)))
q = x(P) * z(Q) * z(R) + z(P) * x(Q) * z(R) + z(P) * z(Q) * x(R) - l^2 * z(P) * z(Q) * z(R)

return p / q

miller関数

入力: $P, Q \in E[m]$

出力: $f_P(Q)$

if (P == Q) {
  return 1
}
T = P
b_i = mの2進展開の列
n = mのビット数
f = 1
for (i = 0; i < n; i = i + 1) {
  f = f^2 * h(T, T, Q)
  T = 2 * T
  if (b_i == 1) {
    f = f * h(T, P, Q)
    T = T + P
  }
}

return f

参考文献