密碼學/素數曲線/雅可比座標

簡介

雅可比座標用於表示素數曲線上的橢圓曲線點 $y^{2}=x^{3}+ax+b.$ 當域反演的成本明顯高於域乘法時，與仿射座標相比，雅可比座標可以提高速度。在雅可比座標中，三元組 $(X,Y,Z)$ 表示仿射點 $({\frac {X}{Z^{2}}},{\frac {Y}{Z^{3}}})$ .

點倍增 (4M + 6S 或 4M + 4S)

令 (X, Y, Z) 是一個點 (不等於無窮遠點)，以雅可比座標表示。那麼它的倍點 (X', Y', Z') 可以透過以下方式計算

if (Y == 0)
  return POINT_AT_INFINITY
S = 4*X*Y^2
M = 3*X^2 + a*Z^4
X' = M^2 - 2*S
Y' = M*(S - X') - 8*Y^4
Z' = 2*Y*Z
return (X', Y', Z')

注意：如果 a = -3，那麼 M 也可以計算為 M = 3*(X + Z^2)*(X - Z^2)，節省了 2 次域平方運算。

重複倍增 ((4m-1)M + (4m+2)S)

令 P=(X, Y, Z) 是一個點 (不等於無窮遠點)，以雅可比座標表示。那麼，在 a = -3 的情況下，它的 "m 倍點" (2^m)P 可以透過以下方式計算

Y = 2*Y
W = Z^4
while(m--)
  if (Y == 0)
    return POINT_AT_INFINITY
  A = 3*(X^2 - W)
  B = X*Y^2
  X = A^2 - 2B
  Z = Z*Y
  if (m)
    W = W*Y^4
  Y = 2*A*(B - X) - Y^4
Y = Y/2
return (X, Y, Z)

可以從修改後的雅可比座標倍點運算中推匯出一個備用重複倍點運算，其成本為 (4m)M + (4m+2)S，適用於任何 a 值。對於較小的 a 值（例如 0 或 -3），成本將降低到 (4m-1)M + (4m+2)S，與上面顯示的演算法相比具有競爭力。

點加 (12M + 4S)

令 (X1, Y1, Z1) 和 (X2, Y2, Z2) 是兩個點 (都不等於無窮遠點)，以雅可比座標表示。那麼它們的和 (X3, Y3, Z3) 可以透過以下方式計算

U = X1*Z2^2
H = X2*Z1^2 - U
S = Y1*Z2^3
R = Y2*Z1^3 - S
if (H == 0)
  if (R == 0)
    return POINT_DOUBLE(X1, Y1, Z1)
  else 
    return POINT_AT_INFINITY
X3 = R^2 - H^3 - 2*U*H^2
Y3 = R*(U*H^2 - X3) - S*H^3
Z3 = H*Z1*Z2
return (X3, Y3, Z3)

J + J -> J ( 12M, 2S) (secp256k1 有 12M, 4S)

U1 = Y2 * Z1
U2 = Y1 * Z2
V1 = X2 * Z1
V2 = X1 * Z2
if (V1 == V2)
  if (U1 == U2)
    return POINT_DOUBLE(X1, Y1, Z1)
  else
    return POINT_AT_INFINITY
U = U1 - U2
V = V1 - V2
W = Z1 * Z2
A = U ^ 2 * W - V ^ 3 - 2 * V ^ 2 * V2
X3 = V * A
Y3 = U * (V ^ 2 * V2 - A) - V ^ 3 * U2
Z3 = V ^ 3 * W
return (X3, Y3, Z3)

混合加 (與仿射點) (8M + 3S)

令 (X1, Y1, Z1) 是一個點，以雅可比座標表示，而 (X2, Y2) 是一個點，以仿射座標表示 (都不等於無窮遠點)。可以從常規的雅可比點加法中輕鬆推匯出一個公式來新增這些點，方法是將每個 "Z2" 替換為 "1"（從而減少四個域乘法和一個域平方運算）。

混合加 (與楚德諾夫斯基點) (11M + 3S)

令 (X1, Y1, Z1) 是一個點，以雅可比座標表示，而 (X2, Y2, Z2, Z2^2, Z2^3) 是一個點，以楚德諾夫斯基座標表示 (都不等於無窮遠點)。那麼可以使用上面給出的加法公式輕鬆計算它們的和 (X3, Y3, Z3) （節省一個域乘法和一個域平方運算）。