Cryptography/Prime Curve/Affine Coordinates

<Cryptography

Point Doubling (1I + 2M + 2S)

Let (x,y) be a point (unequal to the point at infinity) on the elliptic (prime) curve given by the equation y^2 = x^3 + ax + b. Then the point (x',y') := 2*(x,y) can be computed by

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')

Point Addition (1I + 2M + 1S)

Let (x1,y1) and (x2,y2) be two points (both unequal to the point at infinity). Then the point (x3,y3) := (x1,y1) + (x2,y2) can be computed by

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)

Point decompression

The following algorithm calculates for a given x a value y, such that (x,y) is a point on the elliptic curve.

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

Notes:

1. (t|p) denotes the Legendre symbol of t, which decides whether t is a square number or not.
2. The square root can be calculated using the Algorithm of Shanks & Tonelli.