初めに
楕円曲線暗号のための数学1（射影座標）では通常の2次元座標 (x,y) の代わりの射影座標を紹介しました。今回はその亜種のヤコビ（Jacobi）座標を紹介します。
射影座標とヤコビ座標
射影座標の復習
x, y に関する方程式 y^2=x^3+ax+b (a, b \in 𝔽_p) で定義される楕円曲線を E とします。
射影座標は変数 X, Y, Z を用いて x=X/Z, y=Y/Z と x, y をそれぞれ X と Z, Y と Z の比で表す方式でした。ここで X=Y=Z=0 は除外します。
(x, y) に対応する点を [X:Y:Z] と書き、X, Y, Z が満たすべき方程式は Y^2 Z = X^3 + a XZ^2 + b Z^3 です。
無限遠点は Z を 0 に持っていた極限として [X:Y:Z] = [0:1:0] です。
ヤコビ座標
ヤコビ座標は変数 X, Y, Z を用いるのは同じですが、x=X/Z^2, y=Y/Z^3 と少しひねった形をとります。射影座標と同じく [0:0:0] は除外します。
x, y の値を方程式に代入すると Y^2/Z^6 = X^3/Z^6 + a X/Z^2 + b なので両辺に Z^6 を掛けて
がヤコビ座標が満たすべき楕円曲線の方程式となります。これだけなら射影座標よりもややこしくなっただけで利点は見えません。
ヤコビ座標の利用価値を知るにはもう少し準備が必要です。
ヤコビ座標における楕円曲線の点の加算公式
P=(x_1,y_1)=[X_1:Y_1:Z_1], Q=(x_2,y_2)=[X_2:Y_2:Z_2] としてアフィン座標による加法公式に代入します。x_1 \neq x_2 として
L=\frac{y_2-y_1}{x_2-x_1}=\frac{Y_2/Z_2^3-Y_1/Z_1^3}{X_2/Z_2^2-X_1/Z_1^2}=\frac{Z_1^3 Y_2 - Z_2^3 Y_1}{Z_1 Z_2(X_2 Z_1^2-X_1 Z_2^2)}
分子を S, 分母を T として L=S/T として、x=S^2/T^2-(X_1/Z_1^2+X_2/Z_2)=... と計算します。
楕円暗号の数理（小山謙二, 宮地 充子, 内山成憲, 電子情報通信学会論文誌 A, J82-A(8): 1212-1222）から（微調整して）引用すると、R=P+Q=[X_3:Y_3:Z_3] として
x_1 \neq x_2 のときの加算公式
-
U_1=X_1 Z_2^2, U_2=X_2 Z_1^2
-
S_1=Y_1 Z_2^3, S_2=Y_2 Z_1^3
-
H=U_2-U_1, r=S_2-S_1
- X_3=-H^3-2U_1 H^2 + r^2
- Y_3=-S_1 H^3+ r(U_1 H^2-X_3)
- Z_3=Z_1 Z_2 H
2倍算公式（P=Q）
-
s=4 X_1 Y_1^2, m=3 X_1^2+a Z_1^4
- X_3=-2s+m^2
- Y_3=-8 Y_1^4+m(s-X_3)
- Z_3=2Y_1 Z_1
です。そのほかの様々な公式の詳細は Jacobian coordinates for short Weierstrass curvesを見てください。
加算公式の導出（補足）
x_1 \neq x_2 のとき、上記変数の定義を使うと
L=\frac{S_2-S_1}{Z_1 Z_2(U_2-U_1)}=\frac{r}{Z_1 Z_2 H}=\frac{r}{Z_3},
x_1+x_2=\frac{U_1+U_2}{Z_1^2 Z_2^2}=\frac{2 U_1+H}{Z_1^2 Z_2^2}=\frac{(2U_1+H)H^2}{Z_3^2}.
x_3=L^2-(x_1+x_2) より
x_3 Z_3^2=(L^2-(x_1+x_2))Z_3^2=r^2-(2U_1+H)H^2=X_3.
同様に y_3=L(x_1-x_3)-y_1 より
\begin{align*}
\begin{split}
y_3 Z_3^3&= L Z_3 (x_1 Z_3^2 - X_3) - y_1 Z_3^3=r((X_1/Z_1^2)(Z_1 Z_2 H)^2 - X_3) - (Y_1/Z_1^3)(Z_1 Z_2 H)^3\\
&=r(X_1 Z_2^2 H^2 - X_3) - Y_1 Z_1^3 H^3=r(U_1 H^2-X_3)-S_1 H^3.
\end{split}
\end{align*}
P = Q のとき、
L=\frac{3 x_1^2+a}{2 y_1}=\frac{3 X_1^2+a Z_1^4}{2 Y_1 Z_1}=\frac{m}{Z_3}.
x_3 = L^2-2x_1 より
x_3 Z_3^2=m^2 - 2(X_1/Z_1^2) (2 Y_1 Z_1)^2=m^2- 2(4 X_1 Y_1^2) = X_3.
\begin{align*}
\begin{split}
y_3 Z_3^3&=L Z_3(x_1 Z_3^2-X_3)-y_1 Z_3^3=m((X_1/Z_1^2) 4 Y_1^2 Z_1^2 - X_3) - (Y_1/Z_1^3) (8 Y_1^3 Z_1^3)\\
&=m(s-X_3)-8Y_1^4 = Y_3.
\end{split}
\end{align*}
演算コストの比較
射影座標とヤコビ座標を使ったときの計算コストを見てみましょう。
ここでは簡単にするために、有限体上の乗算と2乗算を同じコスト M, 加算を A で表し、楕円曲線の方程式は a=0 とします。ビットコイン、zkSNARKやBLS署名などで使われる楕円曲線はこの仮定を満たします。
このとき楕円曲線の加算 add と2倍算 dbl のコストを表にすると次のようになります。
| 演算 |
射影座標 |
ヤコビ座標 |
| add |
14M+7A |
16M+7A |
| dbl |
12M +11A |
7M+14A |
演算コスト
この表を見ると、add は射影座標の方が速く、dbl はヤコビ座標の方が速いことが分かります。
楕円曲線暗号はスカラー倍算のコストが重要です。前回紹介したように、バイナリ法を使うと、n 倍の計算コストは \log_2(n)(\text{dbl}+\text{add}/2) です。
つまり、dbl の重み（回数）は add の2倍です。この重みを考慮して1ビットあたりのスカラー倍算のコストを計算すると射影座標は (12M+11A)+(14M+7A)/2=19M+14.5A,
ヤコビ座標は (7M+14A)+(16M+7A)/2=15M+17.5A となります。
M は A よりずっと処理が重たいのでdblが速いヤコビ座標を使ったスカラー倍算が高速です。
これがヤコビ座標を導入する理由です。
ヤコビ座標とアフィン座標の併用
バイナリ法によるスカラー倍算（再掲）をよく見ると、加算する値 P は一定です。
def mul(P : Ec, n : int):
bs = bin(n)[2:]
Q = Ec()
for b in bs:
Q = dbl(Q)
if b == '1':
Q = add(Q, P)
return Q
もし、P=[X_1:Y_1:Z_1] がアフィン座標（Z_1=1）ならば、前節の公式は Z_1=1 を仮定して乗算回数を減らせます。
\text{ヤコビ座標} ← \text{add}(\text{ヤコビ座標}, \text{アフィン座標})
スカラー倍算全体で減らせる乗算コストが、一度だけヤコビ座標をアフィン座標に変換するコスト（除算）よりも小さければ、P をアフィン座標にしてから計算する方が速くなります。
Discussion