Prime Curve Affine Coordinates

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:

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