密码学/素数曲线/仿射坐标

<密码学

点倍增 (1I + 2M + 2S)

设 (x,y) 是椭圆（素数）曲线上的一个点（不等于无穷远点），该曲线由方程 y^2 = x^3 + ax + b 给出。则点 (x',y') := 2*(x,y) 可以通过以下方式计算

if (y == 0)
  return POINT_AT_INFINITY
else
  l = (3*x^2 + a) / (2y)
  x' = l^2 - 2x
  y' = l(x - x') - y
  return (x', y')

点加 (1I + 2M + 1S)

设 (x1,y1) 和 (x2,y2) 是两个点（都不等于无穷远点）。则点 (x3,y3) := (x1,y1) + (x2,y2) 可以通过以下方式计算

if (x1 == x2)
  if (y1 != y2)
    return POINT_AT_INFINITY
  else
    return POINT_DOUBLE(x1, y1)
l = (y2 - y1) / (x2 - x1)
x3 = l^2 - x1 - x2
y3 = l(x1 - x3) - y1 = l(x2 - x3) - y2
return (x3, y3)

点解压缩

以下算法为给定的 x 计算一个值 y，使得 (x,y) 是椭圆曲线上的一个点。

t = x^3 + ax + b
if (t|p) >= 0
  return y = sqrt(t)  (the result y = -sqrt(t) would be correct, too)
else 
  return POINT_NOT_EXPANDABLE

注释

1. (t|p) 表示 t 的勒让德符号，它决定 t 是否是一个平方数。
2. 平方根可以使用 Shanks & Tonelli 算法计算。