密码学/素数曲线/雅可比坐标

简介

雅可比坐标用于表示素数曲线上的椭圆曲线点 $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) （节省一个域乘法和一个域平方运算）。