Online Tutorial
4.2 Arithmetic in an Elliptic Curve Group over F2m

Elliptic curve groups over F2m have a finite number of points, and their arithmetic involves no round off error. This combined with the binary nature of the field, F2m arithmetic can be performed very efficiently by a computer.

The following algebraic rules are applied for arithmetic over F2m:

4.2.1 Adding distinct points P and Q

The negative of the point P = (xP, yP) is the point -P = (xP, xP + yP). If P and Q are distinct points such that P is not -Q, then

P + Q = R where

s = (yP - yQ) / (xP + xQ)

xR = s2 + s + xP + xQ + a and yR = s(xP + xR) + xR + yP

As with elliptic curve groups over real numbers, P + (-P) = O, the point at infinity. Furthermore, P + O = P for all points P in the elliptic curve group.

4.2.2 Doubling the point P

If xP = 0, then 2P = O

Provided that xP is not 0,

2P = R where

s = xP + yP / xP

xR = s2 + s + a and yR = xP + (s + 1) * xR

Recall that a is one of the parameters chosen with the elliptic curve and that s is the slope of the line through P and Q

Next