Binary Curve Affine Coordinates

Point Doubling (1D + 1M)

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

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

Note that there are two different ways to compute x'.

Point Halving

Let G be an odd order subgroup of the elliptic curve and P=(x,y) be a point (unequal to the 'point at infinity') in G. Then there exists a unique point Q = (x',y') in G with 2Q = P. If Trace(a) is 1, then Q can be computed as follows:

 find a solution l for the quadratic equation l^2 + l = x + a
 t = y + x*l
 if Trace(t) == 1
   l = l + 1
 else
   t = t + x
 x' = sqrt(t)
 y' = l*x' + t
 return (x', y')

A routine for m-fold repeated halving (of points unequal to the 'point at infinity') is given below.

 if (m == 0)
   return (x, y)
 first = 1
 x' = x
 while(m--)
   find a solution l for the quadratic equation l^2 + l = x' + a
   if (first)
     t = y + x*l
     first = 0
   else
     t = x'*(x' + lq + l)
   if Trace(t) == 1
     lq = l + 1
   else
     lq = l 
     t = t + x'
   x' = sqrt(t)
 y' = lq*x' + t
 return (x', y')

Point addition (1D + 1M)

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 + l + x1 + x2 + a
 y3 = l(x1 + x3) + x3 + y1 = l(x2 + x3) + 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.

 if x == 0
   return y = sqrt(b)
 else
   t = x + a + b/(x^2)
   find a solution l for the quadratic equation l^2 + l = t
   if no such solution exists 
     return POINT_NOT_EXPANDABLE
   else
     return y = l*x  (the result (l + 1)*x would be correct, too)