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 |