# Cryptography/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:

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.