82 3. Elliptic Curve Arithmetic

Group law for supersingular E/F2m : y2 + cy = x3 + ax + b

1.Identity. P + ∞ = ∞ + P = P for all P E(F2m ).

2.Negatives. If P = (x, y) E(F2m ), then (x, y) + (x, y + c) = ∞. The point

(x, y + c) is denoted by − P and is called the negative of P; note that − P is indeed a point in E(F2m ). Also, −∞ = ∞.

3.Point addition. Let P = (x1, y1) E(F2m ) and Q = (x2, y2) E(F2m ), where

P = ±Q. Then P + Q = (x3, y3), where

x3 =	y1	y2		2		y3 =	y1	y2	(x1
		+		+ x1 + x2	and			+		+ x3) + y1	+ c.
	x1	x2					x1	x2
		+						+

4.Point doubling. Let P = (x1, y1) E(F2m ), where P = − P. Then 2P = (x3, y3), where

3 =

c

2

3 =

c

1 +

3

+

1

+

x

x12 + a

and

y

x12 + a

(x

x

)

y

c.

3.1.3Group order

Let E be an elliptic curve defined over Fq . The number of points in E(Fq ), denoted

#E(Fq ), is called the order of E over Fq . Since the Weierstrass equation (3.1) has at most two solutions for each x Fq , we know that #E(Fq ) [1, 2q + 1]. Hasse’s theorem provides tighter bounds for #E(Fq ).

Theorem 3.7 (Hasse) Let E be an elliptic curve defined over Fq . Then q + 1 − 2√q ≤ #E(Fq ) ≤ q + 1 + 2√q.

The interval [q + 1 − 2√q, q + 1 + 2√q] is called the Hasse interval. An alternate formulation of Hasse’s theorem is the following: if E is defined over Fq , then #E(Fq ) = q + 1− t where |t| ≤ 2√q; t is called the trace of E over Fq . Since 2√q is small relative to q, we have #E(Fq ) ≈ q.

The next result determines the possible values for #E(Fq ) as E ranges over all elliptic curves defined over Fq .

Theorem 3.8 (admissible orders of elliptic curves) Let q = pm where p is the characteristic of Fq . There exists an elliptic curve E defined over Fq with #E(Fq ) = q + 1 − t if and only if one of the following conditions holds:

(i)t ≡ 0 (mod p) and t2 ≤ 4q.

(ii)m is odd and either (a) t = 0; or (b) t2 = 2q and p = 2; or (c) t2 = 3q and p = 3.

3.1. Introduction to elliptic curves

83

(iii)m is even and either (a) t2 = 4q; or (b) t2 = q and p ≡ 1 (mod 3); or (c) t = 0 and p ≡ 1 (mod 4).

A consequence of Theorem 3.8 is that for any prime p and integer t satisfying |t| ≤ 2√ p, there exists an elliptic curve E over F p with #E(F p ) = p + 1 − t. This is illustrated in Example 3.9.

Example 3.9 (orders of elliptic curves over√F37) Let p =√37. Table 3.1 lists, for each integer n in the Hasse interval [37 + 1 − 2 37, 37 + 1 + 2 37], the coefficients (a, b) of an elliptic curve E : y2 = x3 + ax + b defined over F37 with #E(F37) = n.

n	(a, b)		n	(a, b)		n	(a, b)		n	(a, b)		n	(a, b)
26	(5,0)		31	(2,8)		36	(1,0)		41	(1,16)		46	(1,11)
27	(0,9)		32	(3,6)		37	(0,5)		42	(1,9)		47	(3,15)
28	(0,6)		33	(1,13)		38	(1,5)		43	(2,9)		48	(0,1)
29	(1,12)		34	(1,18)		39	(0,3)		44	(1,7)		49	(0,2)
30	(2,2)		35	(1,8)		40	(1,2)		45	(2,14)		50	(2,0)

Table 3.1. The admissible orders n = #E(F37) of elliptic curves E : y2 = x3 + ax + b defined over F37.

The order #E(Fq ) can be used to define supersingularity of an elliptic curve.

Definition 3.10 Let p be the characteristic of Fq . An elliptic curve E defined over Fq is supersingular if p divides t, where t is the trace. If p does not divide t, then E is non-supersingular.

If E is an elliptic curve defined over Fq , then E is also defined over any extension Fqn of Fq . The group E(Fq ) of Fq -rational points is a subgroup of the group E(Fqn ) of Fqn -rational points and hence #E(Fq ) divides #E(Fqn ). If #E(Fq ) is known, then

#E(Fqn ) can be efficiently determined by the following result.

Theorem 3.11 Let E be an elliptic curve defined over Fq , and let #E(Fq ) = q + 1 − t. Then #E(Fqn ) = qn + 1 − Vn for all n ≥ 2, where {Vn } is the sequence defined recursively by V0 = 2, V1 = t, and Vn = V1 Vn−1 − qVn−2 for n ≥ 2.

3.1.4Group structure

Theorem 3.12 describes the group structure of E(Fq ). We use Zn to denote a cyclic group of order n.

Theorem 3.12 (group structure of an elliptic curve) Let E be an elliptic curve defined over Fq . Then E(Fq ) is isomorphic to Zn1 Zn2 where n1 and n2 are uniquely determined positive integers such that n2 divides both n1 and q − 1.

84 3. Elliptic Curve Arithmetic

Note that #E(Fq ) = n1n2. If n2 = 1, then E(Fq ) is a cyclic group. If n2 > 1, then E(Fq ) is said to have rank 2. If n2 is a small integer (e.g., n = 2, 3 or 4), we sometimes say that E(Fq ) is almost cyclic. Since n2 divides both n1 and q − 1, one expects that E(Fq ) is cyclic or almost cyclic for most elliptic curves E over Fq .

Example 3.13 (group structure) The elliptic curve E : y2 = x3 + 4x + 20 defined over F29 (cf. Example 3.5) has #E(F29) = 37. Since 37 is prime, E(F29) is a cyclic group and any point in E(F29) except for ∞ is a generator of E(F29). The following shows that the multiples of the point P = (1, 5) generate all the points in E(F29).

0P = ∞	8P = (8, 10)	16P = (0, 22)	24P = (16, 2)	32P = (6, 17)
1P = (1, 5)	9P = (14, 23)	17P = (27, 2)	25P = (19, 16) 33P = (15, 2)
2P = (4, 19)	10P = (13, 23)	18P = (2, 23)	26P = (10, 4)	34P = (20, 26)
3P = (20, 3)	11P = (10, 25)	19P = (2, 6)	27P = (13, 6)	35P = (4, 10)
4P = (15, 27) 12P = (19, 13)		20P = (27, 27) 28P = (14, 6)		36P = (1, 24)
5P = (6, 12)	13P = (16, 27)	21P = (0, 7)	29P = (8, 19)
6P = (17, 19) 14P = (5, 22)		22P = (3, 28)	30P = (24, 7)
7P = (24, 22) 15P = (3, 1)		23P = (5, 7)	31P = (17, 10)

Example 3.14 (group structure) Consider F24 as represented by the reduction polynomial f (z) = z4 + z + 1. The elliptic curve E : y2 + x y = x3 + z3x2 + (z3 + 1) defined

over F24 has #E(F24 ) = 22 (cf. Example 3.6). Since 22 does not have any repeated factors, E(F24 ) is cyclic. The point P = (z3, 1) = (1000, 0001) has order 11; its multiples are shown below.

0P = ∞	3P = (1100, 0000)	6P = (1011, 1001)	9P = (1001, 0110)
1P = (1000, 0001)	4P = (1111, 1011)	7P = (1111, 0100)	10P = (1000, 1001)
2P = (1001, 1111)	5P = (1011, 0010)	8P = (1100, 1100)

3.1.5Isomorphism classes

Recall the definition of isomorphic elliptic curves (Definition 3.4). The relation of isomorphism is an equivalence relation on the set of elliptic curves defined over a finite field K . If two elliptic curves E1 and E2 are isomorphic over K , then their groups E1(K ) and E2(K ) of K -rational points are also isomorphic. However, the converse is not true (cf. Examples 3.16 and 3.17). We present some results on the isomorphism classes of elliptic curves defined over finite fields of characteristic not equal to 2 or 3, and for non-supersingular elliptic curves defined over binary fields.

Theorem 3.15 (isomorphism classes of elliptic curves) Let K = Fq be a finite field with char(K ) = 2, 3.

3.1. Introduction to elliptic curves

85

(i) The elliptic curves
	E1 : y2 = x3 + ax + b							(3.9)
	E2 : y2 = x3 +							(3.10)
		ax + b
4	6						K	such that
defined over K are isomorphic over K if and only if there exists u

u a = a and u b = b. If such a u exists, then the admissible change of variables

(x, y) → (u2 x, u3 y)

transforms equation (3.9) into equation (3.10).

(ii)The number of isomorphism classes of elliptic curves over K is 2q + 6, 2q + 2, 2q + 4, 2q, for q ≡ 1, 5, 7, 11 (mod 12) respectively.

Example 3.16 (isomorphism classes of elliptic curves over F5) Table 3.2 lists the 12 isomorphism classes of elliptic curves over F5. Note that if the groups E1(Fq ) and E2(Fq ) of Fq -rational points are isomorphic, then this does not imply that the elliptic curves E1 and E2 are isomorphic over Fq . For example, the elliptic curves E1 : y2 = x3 + 1 and E2 : y2 = x3 + 2 are not isomorphic over F5, but E1(F5) and E2(F5) both have order 6 and therefore both groups are isomorphic to Z6.

Isomorphism	#E(F5)	Group structure
class		of E(F5)
{y2 = x3 + 1, y2 = x3 + 4}	6	Z6
{y2 = x3 + 2, y2 = x3 + 3}	6	Z6
{y3 = x3 + x}	4	Z2 Z2
{y3 = x3 + 2x}	2	Z2
{y3 = x3 + 3x}	10	Z10
{y3 = x3 + 4x}	8	Z4 Z2
{y2 = x3 + x + 1, y2 = x3 + x + 4}	9	Z9
{y2 = x3 + x + 2, y2 = x3 + x + 3}	4	Z4
{y2 = x3 + 2x + 1, y2 = x3 + 2x + 4}	7	Z7
{y2 = x3 + 3x + 2, y2 = x3 + 3x + 3}	5	Z5
{y2 = x3 + 4x + 1, y2 = x3 + 4x + 4}	8	Z8
{y2 = x3 + 4x + 2, y2 = x3 + 4x + 3}	3	Z3

Table 3.2. Isomorphism classes of elliptic curves E over F5.

Example 3.17 Let p = 73. It is easy to verify using Theorem 3.15 that the elliptic curves

E1 : y2 = x3 + 25x

E2 : y2 = x3 + 53x + 55