86 3. Elliptic Curve Arithmetic

defined over F p are not isomorphic over F p. However, the groups E1(F pm ) and E2(F pm ) of F pm -rational points are isomorphic for every m ≥ 1.

Theorem 3.18 (isomorphism classes of elliptic curves over a binary field)				Let K =
F2m be a binary field.
(i) The non-supersingular elliptic curves
E1 : y2 + x y = x3 + ax2 + b				(3.11)
E2 : y2 + x y = x3 +	ax2 +	b		(3.12)

defined over K are isomorphic over K if and only if b = b and Tr(a) = Tr(a), where Tr is the trace function (see Definition 3.78). If these conditions are satisfied, then there exists s F2m such that a = s2 + s + a, and the admissible change of variables

(x, y) → (x, y + sx)

transforms equation (3.11) into equation (3.12).

(ii)The number of isomorphism classes of non-supersingular elliptic curves over K is 2m+1 − 2. Let γ F2m satisfy Tr(γ ) = 1. A set of representatives of the isomorphism classes is

{y2 + x y = x3 + ax2 + b | a {0, γ }, b F2m }.

(iii)The order #E(F2m ) of the non-supersingular elliptic curve E : y2 + x y = x3 +

γx2 + b is divisible by 2. If Tr(γ ) = 0, then #E(F2m ) is divisible by 4.

3.2Point representation and the group law

Formulas for adding two elliptic points were presented in §3.1 for the elliptic curves y2 = x3 + ax + b defined over a field K of characteristic that is neither 2 nor 3, and for y2 + x y = x3 + ax2 + b defined over a binary field K . For both curves, the formulas for point addition (i.e., adding two distinct finite points that are not negatives of each other) and point doubling require a field inversion and several field multiplications. If inversion in K is significantly more expensive than multiplication, then it may be advantageous to represent points using projective coordinates.

3.2.1Projective coordinates

Let K be a field, and let c and d be positive integers. One can define an equivalence relation on the set K 3\{(0, 0, 0)} of nonzero triples over K by

(X1, Y1, Z1) (X2, Y2, Z2) if X1 = λc X2, Y1 = λd Y2, Z1 = λZ2 for some λ K .

3.2. Point representation and the group law

87

The equivalence class containing (X, Y, Z) K 3\{(0, 0, 0)} is

(X : Y : Z) = {(λc X, λd Y, λZ) : λ K }.

(X : Y : Z) is called a projective point, and (X, Y, Z) is called a representative of (X :

Y : Z). The set of all projective points is denoted by P(K ). Notice that if (X , Y , Z ) (X : Y : Z) then (X : Y : Z ) = (X : Y : Z); that is, any element of an equivalence class can serve as its representative. In particular, if Z = 0, then (X/Zc , Y/Zd , 1) is a representative of the projective point (X : Y : Z), and in fact is the only representative with Z-coordinate equal to 1. Thus we have a 1-1 correspondence between the set of projective points

P(K ) = {(X : Y : Z) : X, Y, Z K , Z = 0} and the set of affine points

A(K ) = {(x, y) : x, y K }.

The set of projective points

P(K )0 = {(X : Y : Z) : X, Y, Z K , Z = 0}

is called the line at infinity since its points do not correspond to any of the affine points. The projective form of Weierstrass equation (3.1) of an elliptic curve E defined over K is obtained by replacing x by X/Zc and y by Y/Zd , and clearing denominators. Now, if (X, Y, Z) K 3\{(0, 0, 0)} satisfies the projective equation then so does any (X , Y , Z ) (X : Y : Z). Therefore it makes sense to say that the projective point (X : Y : Z) lies on E. We thus have a 1-1 correspondence between the affine points in A(K ) that lie on E and the projective points in P(K ) that lie on E. The projective

points in P(K )0 which lie on E are the points at infinity on E.

Example 3.19 (standard projective coordinates) Let c = 1 and d = 1. Then the projective form of the Weierstrass equation

E : y2 + a1x y + a3 y = x3 + a2 x2 + a4 x + a6

defined over K is

Y 2 Z + a1 XY Z + a3Y Z2 = X3 + a2 X2 Z + a4 X Z2 + a6 Z3.

The only point on the line at infinity that also lies on E is (0 : 1 : 0). This projective point corresponds to the point ∞ in Definition 3.1.

Formulas that do not involve field inversions for adding and doubling points in projective coordinates can be derived by first converting the points to affine coordinates, then using the formulas from §3.1 to add the affine points, and finally clearing denominators. Also of use in point multiplication methods (see §3.3) is the addition of two points in mixed coordinates—where the two points are given in different coordinate systems.

88 3. Elliptic Curve Arithmetic

Example 3.20 (addition formulas using Jacobian coordinates) Let c = 2 and d = 3. The projective point (X : Y : Z), Z = 0, corresponds to the affine point (X/Z2, Y/Z3). The projective form of the Weierstrass equation

E : y2 = x3 + ax + b

defined over K is

Y 2 = X3 + a X Z4 + bZ6.

The point at infinity ∞ corresponds to (1 : 1 : 0), while the negative of (X : Y : Z) is

(X : −Y : Z).

Point

doubling. Let P

=

(X

1 : Y1 : Z1) E, and suppose that P = − P. Since P =

2

3

(X1/Z1 : Y1/Z

1 : 1), we can use the doubling formula for E in affine coordinates to

compute 2P =

(X3 : Y3 : 1), obtaining

+

X3 =

Y1

− 2 2 =

2 2

3

X

2

+ a

2

1

X1

(3X12

a Z14)2 − 8X1Y12

Z

14

2

Z

1

4Y

Z

1

3

Z1

1

and

=

X2

& Z1 −

'− Z1

=

2Y1 Z1

& Z1 −

'− Z1

2 Z13

1

+ a

Y3

3

Z14

X1

X3

Y1

3X12

+

a Z

14

X1

X3

Y1

.

Y1

2

3

2

3

and Y

=

X

3 ·

3

3

3

To eliminate denominators in the expressions for X

, we set X3

Z2 and

Y3

=

3 ·

3

=

2Y1 Z1, and obtain the following formulas for computing

Y

Z3 where Z

3

2P = (X3 : Y3 : Z3) in Jacobian coordinates:

X3 = (3X12 + a Z14)2 − 8X1Y12

−

=

+

−

Y3

(3X12

a Z14)(4X1Y12

X3)

8Y14

(3.13)

Z3 =

2Y1 Z1.

By storing some intermediate elements, X3, Y3 and Z3 can be computed using six field squarings and four field multiplications as follows:

A ← Y12, B ← 4X1 · A, C ← 8A2 , D ← 3X12 + a · Z14,

X3 ← D2 − 2B, Y3 ← D · (B − X3) − C, Z3 ← 2Y1 · Z1.

Point addition using mixed Jacobian-affine coordinates. Let P = (X1 : Y1 : Z1) E,

Z1 = 0, and Q = (X2 : Y2 : 1), and suppose that P = ±Q. Since P = (X1/Z12 : Y1/Z13 :

3.2. Point representation and the group law

89

1), we can use the addition formula for E in affine coordinates to compute P + Q =

(X3 : Y3 : 1), obtaining

− Z1 − = &(X2 Z1 − X1)Z1 ' − Z1 −

= X2 − Z12

2

Y2

−

Y1

X

Y

Z3

−

Y

2

X

Z 3

1

1

X3

X1

2

X

2

2

2

X2

and

Y3 =

−

− X3

−

=

1 −

− X3

−

.

X1

2

'

3

2

− X1)Z1

'& Z

2

3

X2

− Z12

& Z

1

Z1

&(X2 Z

1

1

'

Z1

Y2

Y1

X

Y

Y

Z3

Y

X

Y

Z 3

1

1

1

1

2

1

1

To eliminate denominators in the expressions for

3

and Y

3

=

3 ·

3

X

, we set X3

X

Z2

and Y3

=

3 ·

3

=

1

−

X1)Z1, and obtain the following formulas for

Y

Z3 where Z3

(X2 Z2

computing P + Q = (X3 : Y3 : Z3) in Jacobian coordinates:

X3

(Y2 Z13

Y1)2 − (X2 Z12 − X1)2(X1 + X2 Z12)

3 =

2

1 − 1

1

2 1

−

1 −

3 − 1 2

1 −

1

2

= (Y Z3

− Y )(X (X Z2

Y

X )2

X )

Y (X Z2

X )3

(3.14)

Z3 = (X2 Z1 − X1)Z1.

By storing some intermediate elements, X3, Y3 and Z3 can be computed using three field squarings and eight field multiplications as follows:

A ← Z12, B ← Z1 · A,	C ← X2 · A, D ← Y2 · B,	E ← C − X1,
F ← D − Y1,	G ← E2, H ← G · E, I ← X1 · G,
X3 ← F2 − (H + 2I ),	Y3 ← F · (I − X3) − Y1 · H,	Z3 ← Z1 · E.

3.2.2The elliptic curve y2 = x3 + ax + b

This subsection considers coordinate systems and addition formulas for the elliptic curve E : y2 = x3 + ax + b defined over a field K whose characteristic is neither 2 nor 3. Several types of projective coordinates have been proposed.

1. Standard projective coordinates. Here c = 1 and d = 1. The projective point (X : Y : Z), Z = 0, corresponds to the affine point (X/Z, Y/Z). The projective equation of the elliptic curve is

Y 2 Z = X3 + a X Z2 + bZ3.

The point at infinity ∞ corresponds to (0 : 1 : 0), while the negative of (X : Y : Z) is (X : −Y : Z).

90	3. Elliptic Curve Arithmetic
2.	Jacobian projective coordinates. Here c = 2 and d =				3. The projective point
					2		3
	(X : Y : Z), Z = 0, corresponds to the affine point (X/Z					, Y/Z		).The projective
	equation of the elliptic curve is
		Y 2 = X3 + a X Z4 + bZ6.
	The point at infinity ∞ corresponds to (1 : 1 : 0), while the negative of (X : Y : Z)
	is (X : −Y : Z). Doubling	and addition formulas were derived in Example 3.20.
			2	4
	If a = −3, the expression 3X		1 + a Z	1 that occurs in the doubling formula (3.13)
	can be computed using only one field multiplication and one field squaring since
	3X12 − 3Z14 = 3(X1 − Z12) · (X1 + Z12).
	Henceforth, we shall assume that the elliptic curve y2 = x3 + ax + b has a = −3.
	Theorem 3.15 confirms that the selection is without much loss of generality.
	Point doubling can be further accelerated by using the fact that 2Y1 appears sev-
	eral times in (3.13) and trading multiplications by 4 and 8 for divisions by 2. The
	revised doubling formulas are:
	A ← 3(X1 − Z12) · (X1 + Z12),			B ← 2Y1, Z3 ← B · Z1, C ← B2,
	D ← C · X1, X3 ← A2 − 2D, Y3 ← (D − X3) · A − C2/2.

The point doubling and point addition procedures for the case a = −3 are given in Algorithms 3.21 and 3.22 where an effort was made to minimize the number of temporary variables Ti . The algorithms are written in terms of basic field operations; however, specialized routines consisting of integrated basic operations may be advantageous (see §5.1.2 for a concrete example when floating-point hardware is used).

3.Chudnovsky coordinates. Here the Jacobian point (X : Y : Z) is represented as (X : Y : Z : Z2 : Z3). The redundancy in this representation is beneficial in some point multiplication methods where additions are performed in projective coordinates.

3.2. Point representation and the group law

91

Algorithm 3.21 Point doubling (y2 = x3 − 3x + b, Jacobian coordinates)

INPUT: P = (X1 : Y1 : Z1) in Jacobian coordinates on E/K : y2 = x3 − 3x + b. OUTPUT: 2P = (X3 : Y3 : Z3) in Jacobian coordinates.

1.

If P = ∞2

then return(∞).

{T1 ← Z

2

2.

T1 ← Z1 .

1 }

3.

T2 ← X1 − T1.

{T2 ← X1 − Z12}

4.

T1 ← X1 + T1.

{T1 ← X1 + Z12}

5.

T2 ← T2 · T1.

{T2 ← X12 − Z14}

12)(X1 + Z12)}

6.

T2 ← 3T2.

{T2 ← A = 3(X1 − Z

7.

Y3 ← 2Y1.

{Y3 ← B = 2Y1}

8.

Z

3

←

2

·

Z1.

{

Z3

←

B Z1

} 2

Y3

9.

Y3 ← Y3 .

{Y3 ← C = B }

}

10.

3

←

2·

X1.

{

T3

←

2=

C X

T

Y3

D

1

11.

Y3

← Y3 .

{Y3

← C }

12.

Y3

/2.

{

Y

←

C2/2

← Y32

3

2

}

}

13.

X3 ← T2 .

{X3 ← A

14.

T

← 2T3.

{T1 ←

D

15.

1

2

2}

X3 ← X3 − T1.

{X3 ← A

− 2D}

16.

T1

← T3 − X3.

{T1

← D − X3}

17.

T1

← T1 · T2.

{T1

← (D − X3) A}

2

/2}

18.

Y3

← T1 − Y3.

{Y3

← (D − X3) A − C

19. Return(X3 : Y3 : Z3).

Algorithm 3.22 Point addition (y2 = x3 − 3x + b, affine-Jacobian coordinates)

INPUT: P = (X1 : Y1 : Z1) in Jacobian coordinates, Q = (x2, y2) in affine coordinates on E/K : y2 = x3 − 3x + b.

OUTPUT: P + Q = (X3 : Y3 : Z3) in Jacobian coordinates.

1.If Q = ∞ then return(X1 : Y1 : Z1).

2.If P = ∞ then return(x2 : y2 : 1).

3.	T1 ← Z12.	{T1 ← A = Z12}
4.	T2 ← T1 · Z1.	{T2 ← B = Z1 A}
5.	T1 ← T1 · x2.	{T1 ← C = X2 A}
6.	T2 ← T2 · y2.	{T2 ← D = Y2 B}
7.	T1 ← T1 − X1.	{T1 ← E = C − X1}
8.	T2 ← T2 − Y1.	{T2 ← F = D − Y1}

9.If T1 = 0 then

9.1If T2 = 0 then use Algorithm 3.21 to compute

(X3 : Y3 : Z3) = 2(x2 : y2 : 1) and return(X3 : Y3 : Z3).

9.2Else return(∞).

10. Z3 ← Z1 · T1.

{Z3 ← Z1 E}

92 3. Elliptic Curve Arithmetic

11.

T3

← T12.

{T3

← G = E2}

12.

T4

← T3

· T1.

{T4

← H = E3}

13.

T3

← T3

· X1.

{T3

← I = X1 G}

14.

1

←

2

{

T1

←

2I

2}

T

2T3.

15.

X3

← T2 .

{X3 ← F

2

}

16.

X3

← X3

− T1.

{X3 ← F

2

− 2I }

17.

X3

← X3

− T4.

{X3 ← F

− (H + 2I )}

18.

T3

← T3

− X3.

{T3

← I − X3}

19.

T3

← T3

· T2.

{T3

← F(I − X3)}

20.

T4

← T4

· Y1.

{T4

← Y1 H }

21.

Y3 ← T3 − T4.

{Y3 ← F(I − X3) − Y1 H }

22.

Return(X3 : Y3 : Z3).

The field operation counts for point addition and doubling in various coordinate systems are listed in Table 3.3. The notation C1 + C2 → C3 means that the points to be added are in C1 coordinates and C2 coordinates, while their sum is expressed in C3 coordinates; for example, J + A → J is an addition of points in Jacobian and affine coordinates, with result in Jacobian coordinates. We see that Jacobian coordinates yield the fastest point doubling, while mixed Jacobian-affine coordinates yield the fastest point addition. Also useful in some point multiplication algorithms (see Note 3.43) are mixed Jacobian-Chudnovsky coordinates and mixed Chudnovsky-affine coordinates for point addition.

Doubling			General addition			Mixed coordinates
2A → A	1I , 2M, 2S		A + A → A	1I , 2M, 1S		J + A → J	8M, 3S
2P → P	7M, 3S		P + P → P	12M, 2S		J + C → J	11M, 3S
2J → J	4M, 4S		J + J → J	12M, 4S		C + A → C	8M, 3S
2C → C	5M, 4S		C + C → C	11M, 3S

Table 3.3. Operation counts for point addition and doubling on y2 = x3 − 3x + b. A = affine, P = standard projective, J = Jacobian, C = Chudnovsky, I = inversion, M = multiplication, S = squaring.

Repeated doublings

If consecutive point doublings are to be performed, then Algorithm 3.23 may be slightly faster than repeated use of the doubling formula. By working with 2Y until the final step, only one division by 2 is required. A field addition in the loop is eliminated by calculating 3(X − Z2)(X + Z2) as 3(X2 − W ), where W = Z4 is computed at the first doubling and then updated according to W ← W Y 4 before each subsequent doubling.

3.2. Point representation and the group law

93

Algorithm 3.23 Repeated point doubling (y2=x3−3x+b, Jacobian coordinates)

INPUT: P = (X : Y : Z) in Jacobian coordinates on E/K : y2 = x3 − 3x + b, and an integer m > 0.

OUTPUT: 2m P in Jacobian coordinates.

1.If P = ∞ then return(P).

2.Y ← 2Y , W ← Z4.

3.While m > 0 do:

3.1A ← 3(X2 − W ), B ← XY 2.

3.2X ← A2 − 2B, Z ← ZY .

3.3m ← m − 1. If m > 0 then W ← W Y 4.

3.4Y ← 2A(B − X) − Y 4.

4.Return(X, Y/2, Z).

In m consecutive doublings, Algorithm 3.23 trades m − 1 field additions, m − 1 divisions by two, and a multiplication for two field squarings (in comparison with repeated applications of Algorithm 3.21). The strategy can be adapted to the case where a = −3, saving two field squarings in each of m − 1 doublings.

3.2.3The elliptic curve y2 + x y = x3 + ax2 + b

This subsection considers coordinate systems and addition formulas for the nonsupersingular elliptic curve E : y2 + x y = x3 + ax2 + b defined over a binary field K . Several types of projective coordinates have been proposed.

	1.	Standard projective coordinates. Here c = 1 and d = 1. The projective point
		(X : Y : Z), Z = 0, corresponds to the affine point (X/Z, Y/Z). The projective
		equation of the elliptic curve is
		Y 2 Z + XY Z = X3 + a X2 Z + bZ3.
		The point at infinity ∞ corresponds to (0 : 1 : 0), while the negative of (X : Y : Z)
		is (X : X + Y : Z).	3. The projective point
	2.	Jacobian projective coordinates. Here c = 2 and d =
			2		3
		(X : Y : Z), Z = 0, corresponds to the affine point (X/Z		, Y/Z		).The projective

equation of the elliptic curve is

Y 2 + XY Z = X3 + a X2 Z2 + bZ6.

The point at infinity ∞ corresponds to (1 : 1 : 0), while the negative of (X : Y : Z) is (X : X + Y : Z).

3.Lopez´-Dahab (LD) projective coordinates. Here c = 1 and d = 2. The projective point (X : Y : Z), Z = 0, corresponds to the affine point (X/Z, Y/Z2). The

94 3. Elliptic Curve Arithmetic

projective equation of the elliptic curve is

Y 2 + XY Z = X3 Z + a X2 Z2 + bZ4.

The point at infinity ∞ corresponds to (1 : 0 : 0), while the negative of (X : Y : Z) is (X : X + Y : Z). Formulas for computing the double (X3 : Y3 : Z3) of (X1 : Y1 : Z1) are

Z3 ← X12 · Z12, X3 ← X14 + b · Z14, Y3 ← bZ14 · Z3 + X3 · (a Z3 + Y12 + bZ14).

Formulas for computing the sum (X3 : Y3 : Z3) of (X1 : Y1 : Z1) and (X2 : Y2 : 1) are

A ← Y2 · Z12 + Y1, B ← X2 · Z1 + X1, C ← Z1 · B, D ← B2 · (C + a Z12), Z3 ← C2, E ← A · C, X3 ← A2 + D + E, F ← X3 + X2 · Z3,

G ← (X2 + Y2) · Z32, Y3 ← (E + Z3) · F + G.

The point doubling and point addition procedures when a {0, 1} are given in Algorithms 3.24 and 3.25 where an effort was made to minimize the number of temporary variables Ti . Theorem 3.18(ii) confirms that the restriction a {0, 1} is without much loss of generality.

Algorithm 3.24 Point doubling (y2+x y=x3+ax2+b, a {0, 1}, LD coordinates)

INPUT: P = (X1 : Y1 : Z1) in LD coordinates on E/K : y2 + x y = x3 + ax2 + b. OUTPUT: 2P = (X3 : Y3 : Z3) in LD coordinates.

1.	If P = ∞2		then return(∞).		2
2.	T1 ← Z1 .			{T1 ← Z1 }
3.	T2 ← X12.			{T2 ← X12}
4.	Z3 ← T1 · T2.			{Z3 ← X12 Z12}
5.	X3 ← T22.			{X3 ← X14}
6.	T1 ← T12.			{T1 ← Z14}
7.	T2 ← T1 · b.			{T2 ← bZ14}
8.	X3 ← X3 + T2.			{X3 ← X14 + bZ14}
9.	T1 ← Y12.			{T1 ← Y12}
10.	If a = 1 then T1 ← T1 + Z3.			{T1 ← a Z3 + Y12}
11.	T1	← T1 + T2.		{T1	← a Z3 + Y12 + bZ14}
12.	Y3	← X3 · T1.		{Y3	← X3(a Z3 + Y12 + bZ14)}
13.	T1	← T2 · Z3.		{T1	← bZ14 Z3}
14.	Y3	← Y3 + T1.		{Y3	← bZ14 Z3 + X3(a Z3 + Y12 + bZ14)}
15.	Return(X3 : Y3 : Z3).