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: (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.