密碼學/素數曲線/仿射座標

<密碼學

點倍增 (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 演算法計算。