5.2.4 Point Addition (点の加算)

5.2.4 Point Addition (点の加算)

点の加算には, 次の方法が推奨される. 点 (x,y) は射影座標 (projective coordinates) (X, Y, Z) で表し, x = X/Z, y = Y/Z とする.

中立点 (neutral point) は (0,1) であるか, 等価的に任意の非ゼロ Z に対して射影座標では (0, Z, Z) である.

非平方 d をもつねじれのない Edwards 曲線 (すなわち a=1) 上で 2 点 (x3,y3) = (x1,y1)+(x2,y2) を加算する次の公式は, [Faster-ECC] の第 4 節および [EFD-ADD] に記載されている. これらは完全 (complete) である. すなわち, 任意の有効な入力点の対に対して機能する.

                A = Z1*Z2
                B = A^2
                C = X1*X2
                D = Y1*Y2
                E = d*C*D
                F = B-E
                G = B+E
                H = (X1+Y1)*(X2+Y2)
                X3 = A*F*(H-C-D)
                Y3 = A*G*(D-C)
                Z3 = F*G

他の曲線と同様に, 同一点を代入することで倍点公式を得られ, 4 回の乗算を 2 乗に置き換えられる. しかし, これは最適からは程遠い. [Faster-ECC] の第 4 節および [EFD-DBL] に述べられる次の公式は, 複数の乗算を省略できる.

                B = (X1+Y1)^2
                C = X1^2
                D = Y1^2
                E = C+D
                H = Z1^2
                J = E-2*H
                X3 = (B-E)*J
                Y3 = E*(C-D)
                Z3 = E*J