ńņš. 2 |

Let q(x, y) = 0 be the aļ¬ne equation of the conic. In order to apply The-

orem 2.6, we change q(x, y) to its homogeneous form Q(x, y, z). Let (x, y, z)

be a linear form giving the line through X and Y . Then

C(x, y, z) = Q(x, y, z) (x, y, z)

is a homogeneous cubic polynomial. The curve C = 0 contains all of the

points in the table, with the possible exception of Z. It is easily checked that

the only singular points of C are the points of intersection of Q = 0 and

= 0, and the intersection of the two lines comprising Q = 0 in the case

of a degenerate conic. Since none of these points occur among the points

we are considering, the hypotheses of Theorem 2.6 are satisļ¬ed. Therefore,

C(Z) = 0. Since Q(Z) = 0, we must have (Z) = 0, so Z lies on the line

through X and Y . Therefore, X, Y , Z are collinear. This completes the proof

of Pascalā™s theorem.

COROLLARY 2.15 (Pappusā™s Theorem)

Let and m be two distinct lines in the plane. Let A, B, C be distinct points

of and let A , B , C be distinct points of m. Assume that none of these

points is the intersection of and m. Let X be the intersection of AB and

A B, let Y be the intersection of B C and BC , and let Z be the intersection

of CA and C A. Then X, Y, Z are collinear (see Figure 2.5).

PROOF This is the case of a degenerate conic in Theorem 2.13. The

āhexagonā is AB CA BC .

Ā© 2008 by Taylor & Francis Group, LLC

35

SECTION 2.5 OTHER EQUATIONS FOR ELLIPTIC CURVES

C

B

A

Aā™ Bā™

Cā™

Figure 2.5

Pappusā™s Theorem

2.5 Other Equations for Elliptic Curves

In this book, we are mainly using the Weierstrass equation for an elliptic

curve. However, elliptic curves arise in various other guises, and it is worth-

while to discuss these brieļ¬‚y.

2.5.1 Legendre Equation

This is a variant on the Weierstrass equation. Its advantage is that it

allows us to express all elliptic curves over an algebraically closed ļ¬eld (of

characteristic not 2) in terms of one parameter.

PROPOSITION 2.16

Let K be a ļ¬eld of characteristic not 2 and let

y 2 = x3 + ax2 + bx + c = (x ā’ e1 )(x ā’ e2 )(x ā’ e3 )

be an elliptic curve E over K with e1 , e2 , e3 ā K. Let

e3 ā’ e1

x1 = (e2 ā’ e1 )ā’1 (x ā’ e1 ), y1 = (e2 ā’ e1 )ā’3/2 y, Ī»= .

e2 ā’ e1

Then Ī» = 0, 1 and

2

y1 = x1 (x1 ā’ 1)(x1 ā’ Ī»).

PROOF This is a straightforward calculation.

Ā© 2008 by Taylor & Francis Group, LLC

36 CHAPTER 2 THE BASIC THEORY

The parameter Ī» for E is not unique. In fact, each of

Ī»ā’1

1 1 Ī»

{Ī», , 1 ā’ Ī», }

, ,

1ā’Ī» Ī»ā’1

Ī» Ī»

yields a Legendre equation for E. They correspond to the six permutations

of the roots e1 , e2 , e3 . It can be shown that these are the only values of

Ī» corresponding to E, so the map Ī» ā’ E is six-to-one, except where Ī» =

ā’1, 1/2, 2, or Ī»2 ā’ Ī» + 1 = 0 (in these situations, the above set collapses; see

Exercise 2.13).

2.5.2 Cubic Equations

It is possible to start with a cubic equation C(x, y) = 0, over a ļ¬eld K of

characteristic not 2 or 3, that has a point with x, y ā K and ļ¬nd an invertible

change of variables that transforms the equation to Weierstrass form (although

possibly 4A3 + 27B 2 = 0). The procedure is fairly complicated (see [25], [28],

or [84]), so we restrict our attention to a speciļ¬c example.

Consider the cubic Fermat equation

x3 + y 3 + z 3 = 0.

The fact that this equation has no rational solutions with xyz = 0 was conjec-

tured by the Arabs in the 900s and represents a special case of Fermatā™s Last

Theorem, which asserts that the sum of two nonzero nth powers of integers

cannot be a nonzero nth power when n ā„ 3. The ļ¬rst proof in the case n = 3

was probably due to Fermat. Weā™ll discuss some of the ideas for the proof in

the general case in Chapter 15.

Suppose that x3 + y 3 + z 3 = 0 and xyz = 0. Since x3 + y 3 = (x + y)(x2 ā’

xy + y 2 ), we must have x + y = 0. Write

y

x

= u ā’ v.

= u + v,

z z

Then (u + v)3 + (u ā’ v)3 + 1 = 0, so 2u3 + 6uv 2 + 1 = 0. Divide by u3 (since

x + y = 0, we have u = 0) and rearrange to obtain

6(v/u)2 = ā’(1/u)3 ā’ 2.

Let

ā’6 xā’y

z 36v

= ā’12

x1 = , y1 = = 36 .

u x+y u x+y

Then

y1 = x3 ā’ 432.

2

1

It can be shown (this is somewhat nontrivial) that the only rational solutions

to this equation are (x1 , y1 ) = (12, Ā±36), and ā. The case y1 = 36 yields

Ā© 2008 by Taylor & Francis Group, LLC

37

SECTION 2.5 OTHER EQUATIONS FOR ELLIPTIC CURVES

x ā’ y = x + y, so y = 0. Similarly, y1 = ā’36 yields x = 0. The point with

(x1 , y1 ) = ā corresponds to x = ā’y, which means that z = 0. Therefore,

there are no solutions to x3 + y 3 + z 3 = 0 when xyz = 0.

2.5.3 Quartic Equations

Occasionally, we will meet curves deļ¬ned by equations of the form

v 2 = au4 + bu3 + cu2 + du + e, (2.6)

with a = 0. If we have a point (p, q) lying on the curve with p, q ā K, then

the equation (when it is nonsingular) can be transformed into a Weierstrass

equation by an invertible change of variables that uses rational functions with

coeļ¬cients in the ļ¬eld K. Note that an elliptic curve E deļ¬ned over a ļ¬eld K

always has a point in E(K), namely ā (whose projective coordinates (0 : 1 : 0)

certainly lie in K). Therefore, if we are going to transform a curve C into

Weierstrass form in such a way that all coeļ¬cients of the rational functions

describing the transformation lie in K, then we need to start with a point on

C that has coordinates in K.

There are curves of the form (2.6) that do not have points with coordinates

in K. This phenomenon will be discussed in more detail in Chapter 8.

Suppose we have a curve deļ¬ned by an equation (2.6) and suppose we have

a point (p, q) lying on the curve. By changing u to u + p, we may assume

p = 0, so the point has the form (0, q).

First, suppose q = 0. If d = 0, then the curve has a singularity at (u, v) =

(0, 0). Therefore, assume d = 0. Then

1 1 1

v2

) = d( )3 + c( )2 + b( ) + a.

(

u2 u u u

This can be easily transformed into a Weierstrass equation in d/u and dv/u2 .

The harder case is when q = 0. We have the following result.

THEOREM 2.17

Let K be a ļ¬eld of characteristic not 2. Consider the equation

v 2 = au4 + bu3 + cu2 + du + q 2

with a, b, c, d, q ā K. Let

4q 2 (v + q) + 2q(du + cu2 ) ā’ (d2 u2 /2q)

2q(v + q) + du

x= , y= .

u2 u3

Deļ¬ne

a2 = c ā’ (d2 /4q 2 ), a4 = ā’4q 2 a,

a1 = d/q, a3 = 2qb, a6 = a2 a4 .

Ā© 2008 by Taylor & Francis Group, LLC

38 CHAPTER 2 THE BASIC THEORY

Then

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .

The inverse transformation is

2q(x + c) ā’ (d2 /2q) u(ux ā’ d)

v = ā’q +

u= , .

y 2q

The point (u, v) = (0, q) corresponds to the point (x, y) = ā and (u, v) =

(0, ā’q) corresponds to (x, y) = (ā’a2 , a1 a2 ā’ a3 ).

PROOF Most of the proof is a āstraightforwardā calculation that we omit.

For the image of the point (0, ā’q), see [28].

Example 2.2

Consider the equation

v 2 = u4 + 1. (2.7)

Then a = 1, b = c = d = 0, and q = 1. If

2(v + 1) 4(v + 1)

x= , y= ,

u2 u3

then we obtain the elliptic curve E given by

y 2 = x3 ā’ 4x.

The inverse transformation is

v = ā’1 + (2x3 /y 2 ).

u = 2x/y,

The point (u, v) = (0, 1) corresponds to ā on E, and (u, v) = (0, ā’1) corre-

sponds to (0, 0). We will show in Chapter 8 that

E(Q) = {ā, (0, 0), (2, 0), (ā’2, 0)}.

These correspond to (u, v) = (0, 1), (0, ā’1), and points at inļ¬nity. Therefore,

the only ļ¬nite rational points on the quartic curve are (u, v) = (0, Ā±1). It is

easy to deduce from this that the only integer solutions to

a4 + b4 = c2

satisfy ab = 0. This yields Fermatā™s Last Theorem for exponent 4. We will

discuss this in more detail in Chapter 8.

It is worth considering brieļ¬‚y the situation at inļ¬nity in u, v. If we make

the equation (2.7) homogeneous, we obtain

F (u, v, w) = v 2 w2 ā’ u4 ā’ w4 = 0.

Ā© 2008 by Taylor & Francis Group, LLC

39

SECTION 2.5 OTHER EQUATIONS FOR ELLIPTIC CURVES

The points at inļ¬nity have w = 0. To ļ¬nd them, we set w = 0 and get 0 = u4 ,

which means u = 0. We thus ļ¬nd only the point (u : v : w) = (0 : 1 : 0). But

we have two points, namely (2, 0) and (ā’2, 0) in the corresponding Weierstrass

model. The problem is that (u : v : w) = (0 : 1 : 0) is a singular point in the

quartic model. At this point we have

Fu = Fv = Fw = 0.

What is happening is that the curve intersects itself at the point (u : v :

w) = (0 : 1 : 0). One branch of the curve is v = +u2 1 + (1/u)4 and the

other is v = ā’u2 1 + (1/u)4 . For simplicity, letā™s work with real or complex

numbers. If we substitute the second of these expressions into x = 2(v + 1)/u2

and take the limit as u ā’ ā, we obtain

2(1 ā’ u2 1 + (1/u)4 )

2(v + 1)

ā’ ā’2.

x= =

u2 u2

If we use the other branch, we ļ¬nd x ā’ +2. So the transformation that

changes the quartic equation into the Weierstrass equation has pulled apart

the two branches (the technical term is āresolved the singularitiesā) at the

singular point.

2.5.4 Intersection of Two Quadratic Surfaces

The intersection of two quadratic surfaces in three-dimensional space, along

with a point on this intersection, is usually an elliptic curve. Rather than work

in full generality, weā™ll consider pairs of equations of the form

au2 + bv 2 = e, cu2 + dw2 = f,

where a, b, c, d, e, f are nonzero elements of a ļ¬eld K of characteristic not 2.

Each separate equation may be regarded as a surface in uvw-space, and they

intersect in a curve. Weā™ll show that if we have a point P in the intersection,

then we can transform this curve into an elliptic curve in Weierstrass form.

Before analyzing the intersection of these two surfaces, letā™s consider the

ļ¬rst equation by itself. It can be regarded as giving a curve C in the uv-

plane. Let P = (u0 , v0 ) be a point on C. Let L be the line through P with

slope m:

u = u0 + t, v = v0 + mt.

We want to ļ¬nd the other point where L intersects C. See Figure 2.6.

Substitute into the equation for C and use the fact that au2 + bv0 = e to

2

0

obtain

a(2u0 t + t2 ) + b(2v0 mt + m2 t2 ) = 0.

Ā© 2008 by Taylor & Francis Group, LLC

40 CHAPTER 2 THE BASIC THEORY

u,v

C

L

u0 ,v0

Figure 2.6

Since t = 0 corresponds to (u0 , v0 ), we factor out t and obtain

2au0 + 2bv0 m

t=ā’ .

a + bm2

Therefore,

2amu0 + 2bv0 m2

2au0 + 2bv0 m

u = u0 ā’ v = v0 ā’

, .

a + bm2 a + bm2

We make the convention that m = ā yields (u0 , ā’v0 ), which is what we get

if we are working with real numbers and let m ā’ ā. Also, possibly the

denominator a + bm2 vanishes, in which case we get points āat inļ¬nityā in the

uv-projective plane (see Exercise 2.14).

Note that if (u, v) is any point on C with coordinates in K, then the slope

m of the line through (u, v) and P is in K (or is inļ¬nite). We have there-

fore obtained a bijection, modulo a few technicalities, between values of m

(including ā) and points on C (including points at inļ¬nity). The main point

is that we have obtained a parameterization of the points on C. A similar

procedure works for any conic section containing a point with coordinates in

K.

Which value of m corresponds to the original point (u0 , v0 )? Let m be the

slope of the tangent line at (u0 , v0 ). The second point of intersection of the

tangent line with the curve is again the point (u0 , v0 ), so this slope is the

desired value of m. The value m = 0 yields the point (ā’u0 , v0 ). This can be

seen from the formulas, or from the fact that the line through (ā’u0 , v0 ) and

(u0 , v0 ) has slope 0.

We now want to intersect C, regarded as a ācylinderā in uvw-space, with

the surface cu2 + dw2 = f . Substitute the expression just obtained for u to

obtain

2

2au0 + 2bv0 m

2

dw = f ā’ c u0 ā’ .

a + bm2

Ā© 2008 by Taylor & Francis Group, LLC

41

SECTION 2.5 OTHER EQUATIONS FOR ELLIPTIC CURVES

This may be rewritten as

d(w(a + bm2 ))2 = (a + bm2 )2 f ā’ c(bu0 m2 ā’ 2bv0 m ā’ au0 )2

= (b2 f ā’ cb2 u2 )m4 + Ā· Ā· Ā· .

0

This may now be changed to Weierstrass form by the procedure given ear-

lier. Note that the leading coeļ¬cient b2 f ā’ cb2 u2 equals b2 dw0 . If w0 = 0,

2

0

then fourth degree polynomial becomes a cubic polynomial, so the equation

just obtained is easily put into Weierstrass form. The leading term of this

cubic polynomial vanishes if and only if v0 = 0. But in this case, the point

(u0 , v0 , w0 ) = (u0 , 0, 0) is a singular point of the uvw curve ā“ a situation that

we should avoid (see Exercise 2.15).

The procedure for changing āsquare = degree four polynomialā into Weier-

strass form requires a point satisfying this equation. We could let m be the

slope of the tangent line at (u0 , v0 ), which corresponds to the point (u0 , v0 ).

The formula of Theorem 2.17 then requires that we shift the value of m to

obtain m = 0. Instead, itā™s easier to use m = 0 directly, since this value

corresponds to (ā’u0 , v0 ), as pointed out above.

Example 2.3

Consider the intersection

u2 + v 2 = 2, u2 + 4w2 = 5.

Let (u0 , v0 , w0 ) = (1, 1, 1). First, we parameterize the solutions to u2 +v 2 = 2.

Let u = 1 + t, v = 1 + mt. This yields

(1 + t)2 + (1 + mt)2 = 2,

which yields t(2 + 2m) + t2 (1 + m2 ) = 0. Discarding the solution t = 0, we

obtain t = ā’(2 + 2m)/(1 + m2 ), hence

m2 ā’ 2m ā’ 1 1 ā’ 2m ā’ m2

2 + 2m 2 + 2m

u=1ā’ v =1ā’m

= , = .

1 + m2 1 + m2 1 + m2 1 + m2

Note that m = ā’1 corresponds to (u, v) = (1, 1) (this is because the tangent

at this point has slope m = ā’1). Substituting into u2 + 4w2 = 5 yields

4(w(1 + m2 ))2 = 5(1 + m2 )2 ā’ (m2 ā’ 2m ā’ 1)2 = 4m4 + 4m3 + 8m2 ā’ 4m + 4.

Letting r = w(1 + m2 ) yields

r2 = m4 + m3 + 2m2 ā’ m + 1.

In Theorem 2.17, we use q = 1. The formulas then change this curve to the

generalized Weierstrass equation

7

y 2 ā’ xy + 2y = x3 + x2 ā’ 4x ā’ 7.

4

Ā© 2008 by Taylor & Francis Group, LLC

42 CHAPTER 2 THE BASIC THEORY

Completing the square yields

y1 = x3 + 2x2 ā’ 5x ā’ 6,

2

where y1 = y + 1 ā’ 1 x.

2

2.6 Other Coordinate Systems

The formulas for adding two points on an elliptic curve in Weierstrass form

require 2 multiplications, 1 squaring, and 1 inversion in the ļ¬eld. Although

ļ¬nding inverses is fast, it is much slower than multiplication. In [27, p. 282],

it is estimated that inversion takes between 9 and 40 times as long as multi-

plication. Moreover, squaring takes about 0.8 the time of multiplication. In

many situations, this distinction makes no diļ¬erence. However, if a central

computer needs to verify many signatures in a second, such distinctions can

become relevant. Therefore, it is sometimes advantageous to avoid inversion

in the formulas for point addition. In this section, we discuss a few alternative

formulas where this can be done.

2.6.1 Projective Coordinates

A natural method is to write all the points as points (x : y : z) in projective

space. By clearing denominators in the standard formulas for addition, we

obtain the following:

Let Pi = (xi : yi : zi ), i = 1, 2, be points on the elliptic curve y 2 z =

x3 + Axz 2 + Bz 3 . Then

(x1 : y1 : z1 ) + (x2 : y2 : z2 ) = (x3 : y3 : z3 ),

where x3 , y3 , z3 are computed as follows: When P1 = Ā±P2 ,

w = u2 z1 z2 ā’ v 3 ā’ 2v 2 x1 z2 ,

u = y 2 z1 ā’ y 1 z2 , v = x2 z1 ā’ x1 z2 ,

y3 = u(v 2 x1 z2 ā’ w) ā’ v 3 y1 z2 , z3 = v 3 z 1 z 2 .

x3 = vw,

When P1 = P2 ,

t = Az1 + 3x2 ,

2

w = t2 ā’ 8v,

u = y1 z 1 , v = ux1 y1 ,

1

y3 = t(4v ā’ w) ā’ 8y1 u2 ,

2

z3 = 8u3 .

x3 = 2uw,

When P1 = ā’P2 , we have P1 + P2 = ā.

Point addition takes 12 multiplications and 2 squarings, while point dou-

bling takes 7 multiplications and 5 squarings. No inversions are needed. Since

Ā© 2008 by Taylor & Francis Group, LLC

43

SECTION 2.6 OTHER COORDINATE SYSTEMS

addition and subtraction are much faster than multiplication, we do not con-

sider them in our analysis. Similarly, multiplication by a constant is not

included.

2.6.2 Jacobian Coordinates

A modiļ¬cation of projective coordinates leads to a faster doubling proce-

dure. Let (x : y : z) represent the aļ¬ne point (x/z 2 , y/z 3 ). This is somewhat

natural since, as weā™ll see in Chapter 11, the function x has a double pole at ā

and the function y has a triple pole at ā. The elliptic curve y 2 = x3 + Ax + B

becomes

y 2 = x3 + Axz 4 + Bz 6 .

The point at inļ¬nity now has the coordinates ā = (1 : 1 : 0).

Let Pi = (xi : yi : zi ), i = 1, 2, be points on the elliptic curve y 2 =

x3 + Axz 4 + Bz 6 . Then

(x1 : y1 : z1 ) + (x2 : y2 : z2 ) = (x3 : y3 : z3 ),

where x3 , y3 , z3 are computed as follows: When P1 = Ā±P2 ,

2 2 3 3

v = s ā’ r, w = u ā’ t,

r = x1 z 2 , s = x2 z1 , t = y 1 z2 , u = y2 z 1 ,

x3 = ā’v 3 ā’ 2rv 2 + w2 , y3 = ā’tv 3 + (rv 2 ā’ x3 )w, z3 = vz1 z2 .

When P1 = P2 ,

2

w = 3x2 + Az1 ,

4

v = 4x1 y1 , 1

x3 = ā’2v + w2 , 4

y3 = ā’8y1 + (v ā’ x3 )w, z3 = 2y1 z1 .

When P1 = ā’P2 , we have P1 + P2 = ā.

Addition of points takes 12 multiplications and 4 squarings. Doubling takes

3 multiplications and 6 squarings. There are no inversions.

When A = ā’3, a further speed-up is possible in doubling: we have w =

3(x2 ā’ z1 ) = 3(x1 + z1 )(x1 ā’ z1 ), which can be computed in one squaring and

4 2 2

1

one multiplication, rather than in 3 squarings. Therefore, doubling takes only

4 multiplications and 4 squarings in this case. The elliptic curves in NISTā™s

list of curves over ļ¬elds Fp ([86], [48, p. 262]) have A = ā’3 for this reason.

There are also situations where a point in one coordinate system can be

eļ¬ciently added to a point in another coordinate system. For example, it takes

only 8 multiplications and 3 squarings to add a point in Jacobian coordinates

to one in aļ¬ne coordinates. For much more on other choices for coordinates

and on eļ¬cient point addition, see [48, Sections 3.2, 3.3] and [27, Sections

13.2, 13.3].

Ā© 2008 by Taylor & Francis Group, LLC

44 CHAPTER 2 THE BASIC THEORY

2.6.3 Edwards Coordinates

In [36], Harold Edwards describes a form for elliptic curves that has certain

computational advantages. The case with c = 1, d = ā’1 occurs in work of

Euler and Gauss. Edwards restricts to the case d = 1. The more general form

has subsequently been discussed by Bernstein and Lange [11].

PROPOSITION 2.18

Let K be a ļ¬eld of characteristic not 2. Let c, d ā K with c, d = 0 and d not

a square in K. The curve

u2 + v 2 = c2 (1 + du2 v 2 )

C:

is isomorphic to the elliptic curve

y 2 = (x ā’ c4 d ā’ 1)(x2 ā’ 4c4 d)

E:

via the change of variables

4c2 (w ā’ c) + 2c(c4 d + 1)u2

ā’2c(w ā’ c)

x= , y= ,

u2 u3

where w = (c2 du2 ā’ 1)v.

The point (0, c) is the identity for the group law on C, and the addition law

is

v 1 v2 ā’ u 1 u 2

u 1 v2 + u 2 v1

(u1 , v1 ) + (u2 , v2 ) = ,

c(1 + du1 u2 v1 v2 ) c(1 ā’ du1 u2 v1 v2 )

for all points (ui , vi ) ā C(K). The negative of a point is ā’(u, v) = (ā’u, v).

PROOF Write the equation of the curve as

w2

u2 ā’ c2 = c2 du2 ā’ 1 v 2 = .

c2 du2 ā’ 1

This yields the curve

w2 = c2 du4 ā’ (c4 d + 1)u2 + c2 .

The formulas in Section 2.5.3 then change this curve to Weierstrass form. The

formula for the addition law can be obtained by a straightforward computa-

tion.

It remains to show that the addition law is deļ¬ned for all points in C(K).

In other words, we need to show that the denominators are nonzero. Suppose

Ā© 2008 by Taylor & Francis Group, LLC

45

SECTION 2.7 THE j-INVARIANT

du1 v1 u2 v2 = ā’1. Then ui , vi = 0 and u1 v1 = ā’1/du2 v2 . Substituting into

the formula for C yields

u2 + v22

1 2

u2 2 2

+ v1 =c 1+ 2 2 = 2.

1

du2 v2

du2 v2 2

Therefore,

2

(u1 + v1 ) = u2 + v1 + 2u1 v1

2

1

2

u2 + v2 ā’ 2u2 v2

2

1 (u2 ā’ v2 )

1 2

= = .

d (u2 v2 )2

u2 v2

2

d 2

Since d is not a square, this must reduce to 0 = 0, so u1 + v1 = 0.

Similarly,

2

1 (u2 + v2 )

2

(u1 ā’ v1 ) = ,

d (u2 v2 )2

which implies that u1 ā’ v1 = 0. Therefore, u1 = v1 = 0, which is a contradic-

tion.

The case where du1 v1 u2 v2 = 1 similarly produces a contradiction. There-

fore, the addition formula is always deļ¬ned for points in C(K).

An interesting feature is that there are not separate formulas for 2P and

P1 + P2 when P1 = P2 .

The formula for adding points can be written in projective coordinates. The

resulting computation takes 10 multiplications and 1 squaring for both point

addition and point doubling.

Although any elliptic curve can be put into the form of the proposition over

an algebraically closed ļ¬eld, this often cannot be done over the base ļ¬eld. An

easy way to see this is that there is a point of order 2. In fact, the point (c, 0)

on C has order 4 (Exercise 2.7), so a curve that can be put into Edwards form

over a ļ¬eld must have a point of order 4 deļ¬ned over that ļ¬eld.

2.7 The j-invariant

Let E be the elliptic curve given by y 2 = x3 + Ax + B, where A, B are

elements of a ļ¬eld K of characteristic not 2 or 3. If we let

x1 = Āµ2 x, y1 = Āµ3 y, (2.8)

Ć—

with Āµ ā K , then we obtain

y1 = x3 + A1 x1 + B1 ,

2

1

Ā© 2008 by Taylor & Francis Group, LLC

46 CHAPTER 2 THE BASIC THEORY

with

A1 = Āµ4 A, B1 = Āµ6 B.

(In the generalized Weierstrass equation y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x +

a6 , this change of variables yields new coeļ¬cients Āµi ai . This explains the

numbering of the coeļ¬cients.)

Deļ¬ne the j-invariant of E to be

4A3

j = j(E) = 1728 .

4A3 + 27B 2

Note that the denominator is the negative of the discriminant of the cubic,

hence is nonzero by assumption. The change of variables (2.8) leaves j un-

changed. The converse is true, too.

THEOREM 2.19

Let y1 = x3 + A1 x1 + B1 and y2 = x3 + A2 x2 + B2 be two elliptic curves with

2 2

1 2

j-invariants j1 and j2 , respectively. If j1 = j2 , then there exists Āµ = 0 in K

(= algebraic closure of K) such that

A2 = Āµ4 A1 , B2 = Āµ6 B1 .

The transformation

x2 = Āµ2 x1 , y2 = Āµ3 y1

takes one equation to the other.

PROOF First, assume that A1 = 0. Since this is equivalent to j1 = 0, we

also have A2 = 0. Choose Āµ such that A2 = Āµ4 A1 . Then

4A3 4A3 4Āµā’12 A3 4A3

2 1 2 2

3 + 27B 2 = 4A3 + 27B 2 = 4Āµā’12 A3 + 27B 2 = 4A3 + 27Āµ12 B 2 ,

4A2 2 1 1 2 1 2 1

which implies that

B2 = (Āµ6 B1 )2 .

2

Therefore B2 = Ā±Āµ6 B1 . If B2 = Āµ6 B1 , weā™re done. If B2 = ā’Āµ6 B1 , then

change Āµ to iĀµ (where i2 = ā’1). This preserves the relation A2 = Āµ4 A1 and

also yields B2 = Āµ6 B1 .

If A1 = 0, then A2 = 0. Since 4A3 + 27Bi = 0, we have B1 , B2 = 0. Choose

2

i

Āµ such that B2 = Āµ6 B1 .

There are two special values of j that arise quite often:

1. j = 0: In this case, the elliptic curve E has the form y 2 = x3 + B.

2. j = 1728: In this case, the elliptic curve has the form y 2 = x3 + Ax.

Ā© 2008 by Taylor & Francis Group, LLC

47

SECTION 2.8 ELLIPTIC CURVES IN CHARACTERISTIC 2

The ļ¬rst one, with B = ā’432, was obtained in Section 2.5.2 from the Fermat

equation x3 + y 3 + z 3 = 0. The second curve, once with A = ā’25 and once

with A = ā’4, appeared in Chapter 1.

The curves with j = 0 and with j = 1728 have automorphisms (bijective

group homomorphisms from the curve to itself) other than the one deļ¬ned by

(x, y) ā’ (x, ā’y), which is an automorphism for any elliptic curve in Weier-

strass form.

1. y 2 = x3 + B has the automorphism (x, y) ā’ (Ī¶x, ā’y), where Ī¶ is a

nontrivial cube root of 1.

2. y 2 = x3 + Ax has the automorphism (x, y) ā’ (ā’x, iy), where i2 = ā’1.

(See Exercise 2.17.)

Note that the j-invariant tells us when two curves are isomorphic over an

algebraically closed ļ¬eld. However, if we are working with a nonalgebraically

closed ļ¬eld K, then it is possible to have two curves with the same j-invariant

that cannot be transformed into each other using rational functions with co-

eļ¬cients in K. For example, both y 2 = x3 ā’ 25x and y 2 = x3 ā’ 4x have

j = 1728. The ļ¬rst curve has inļ¬nitely points with coordinates in Q, for

example, all integer multiples of (ā’4, 6) (see Section 8.4). The only rational

points on the second curve are ā, (2, 0), (ā’2, 0), and (0, 0) (see Section 8.4).

Therefore, we cannot change one curve into the other using only rational func-

ā

tions deļ¬ned over Q. Of course, we can use the ļ¬eld ā 10) to change one

Q(

curve to the other via (x, y) ā’ (Āµ2 x, Āµ3 y), where Āµ = 10/2.

If two diļ¬erent elliptic curves deļ¬ned over a ļ¬eld K have the same j-

invariant, then we say that the two curves are twists of each other.

Finally, we note that j is the j-invariant of

3j 2j

y 2 = x3 + x+ (2.9)

1728 ā’ j 1728 ā’ j

when j = 0, 1728. Since y 2 = x3 + 1 and y 2 = x3 + x have j-invariants 0

and 1728, we ļ¬nd the j-invariant gives a bijection between elements of K and

K-isomorphism classes of elliptic curves deļ¬ned over K (that is, each j ā K

corresponds to an elliptic curve deļ¬ned over K, and any two elliptic curves

deļ¬ned over K and with the same j-invariant can be transformed into each

other by a change of variables (2.8) deļ¬ned over K).

If the characteristic of K is 2 or 3, the j-invariant can also be deļ¬ned, and

results similar to the above one hold. See Section 2.8 and Exercise 2.18.

2.8 Elliptic Curves in Characteristic 2

Since we have been using the Weierstrass equation rather than the gener-

alized Weierstrass equation in most of the preceding sections, the formulas

Ā© 2008 by Taylor & Francis Group, LLC

48 CHAPTER 2 THE BASIC THEORY

given do not apply when the ļ¬eld K has characteristic 2. In this section, we

sketch what happens in this case.

Note that the Weierstrass equation is singular. Let f (x, y) = y 2 ā’ x3 ā’

Ax ā’ B. Then fy = 2y = 0, since 2 = 0 in characteristic 2. Let x0 be a

root (possibly in some extension of K) of fx = ā’3x2 ā’ A = 0 and let y0

be the square root of x3 + Ax0 + B. Then (x0 , y0 ) lies on the curve and

0

fx (x0 , y0 ) = fy (x0 , y0 ) = 0.

Therefore, we work with the generalized Weierstrass equation for an elliptic

curve E:

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .

If a1 = 0, then the change of variables

y = a3 y1 + aā’3 (a2 a4 + a2 )

x = a2 x1 + (a3 /a1 ),

1 1 1 3

1

changes the equation to the form

y1 + x1 y1 = x3 + a2 x2 + a6 .

2

1 1

This curve is nonsingular if and only if a6 = 0. The j-invariant in this case

is deļ¬ned to be 1/a6 (more precisely, there are formulas for the j-invariant of

the generalized Weierstrass form, and these yield 1/a6 in this case).

If a1 = 0, we let x = x1 + a2 , y = y1 to obtain an equation of the form

y1 + a3 y1 = x3 + a4 x1 + a6 .

2

1

This curve is nonsingular if and only if a3 = 0. The j-invariant is deļ¬ned to

be 0.

Letā™s return to the generalized Weierstrass equation and look for points at

inļ¬nity. Make the equation homogeneous:

y 2 z + a1 xyz + a3 yz 2 = x3 + a2 x2 z + a4 xz 2 + a6 z 3 .

Now set z = 0 to obtain 0 = x3 . Therefore, ā = (0 : 1 : 0) is the only point

at inļ¬nity on E, just as with the standard Weierstrass equation. A line L

through (x0 , y0 ) and ā is a vertical line x = x0 . If (x0 , y0 ) lies on E then the

other point of intersection of L and E is (x0 , ā’a1 x0 ā’ a3 ā’ y0 ). See Exercise

2.9.

We can now describe addition of points. Of course, P + ā = P , for all

points P . Three points P, Q, R add to ā if and only if they are collinear. The

negation of a point is given by

ā’(x, y) = (x, ā’a1 x ā’ a3 ā’ y).

To add two points P1 and P2 , we therefore proceed as follows. Draw the line

L through P1 and P2 (take the tangent if P1 = P2 ). It will intersect E in a

third point P3 . Now compute P3 = ā’P3 by the formula just given (do not

simply reļ¬‚ect across the x-axis). Then P1 + P2 = P3 .

Ā© 2008 by Taylor & Francis Group, LLC

49

SECTION 2.8 ELLIPTIC CURVES IN CHARACTERISTIC 2

The proof that this addition law is associative is the same as that given in

Section 2.4. The points on E, including ā, therefore form an abelian group.

Since we will need it later, letā™s look at the formula for doubling a point in

characteristic 2. To keep the formulas from becoming too lengthy, weā™ll treat

separately the two cases obtained above.

1. y 2 + xy = x3 + a2 x2 + a6 . Rewrite this as y 2 + xy + x3 + a2 x2 + a6 = 0

(remember, we are in characteristic 2). Implicit diļ¬erentiation yields

xy + (y + x2 ) = 0

(since 2 = 0 and 3 = 1). Therefore the slope of the line L through

P = (x0 , y0 ) is m = (y0 + x2 )/x0 . The line is

0

y = m(x ā’ x0 ) + y0 = mx + b

for some b. Substitute to ļ¬nd the intersection (x1 , y1 ) of L and E:

0 = (mx + b)2 + x(mx + b) + x3 + a2 x2 + a6 = x3 + (m2 + m + a2 )x2 + Ā· Ā· Ā· .

The sum x0 + x0 + x1 of the roots is (m2 + m + a2 ), so we obtain

y0 + x4 + x0 y0 + x3 + a2 x2

2

x4 + a6

0 0 0

= 02

2

x1 = m + m + a2 = 2

x0 x0

(since y0 = x0 y0 + x3 + a2 x2 + a6 ). The y-coordinate of the intersection

2

0 0

is y1 = m(x1 ā’ x0 ) + y0 . The point (x1 , y1 ) equals ā’2P . Therefore

2P = (x2 , y2 ), with

x2 = (x4 + a6 )/x2 , y2 = ā’x1 ā’ y1 = x1 + y1 .

0 0

2. y 2 + a3 y = x3 + a4 x + a6 . Rewrite this as y 2 + a3 y + x3 + a4 x + a6 = 0.

Implicit diļ¬erentiation yields

a3 y + (x2 + a4 ) = 0.

Therefore the tangent line L is

x2 + a4

m= 0

y = m(x ā’ x0 ) + y0 , with .

a3

Substituting and solving, as before, ļ¬nds the point of intersection (x1 , y1 )

of L and E, where

x4 + a2

x1 = m = 0 2 4

2

a3

and y1 = m(x1 ā’ x0 ) + y0 . Therefore, 2P = (x2 , y2 ) with

x2 = (x4 + a2 )/a2 , y2 = a3 + y1 .

0 4 3

Ā© 2008 by Taylor & Francis Group, LLC

50 CHAPTER 2 THE BASIC THEORY

2.9 Endomorphisms

The main purpose of this section is to prove Proposition 2.21, which will

be used in the proof of Hasseā™s theorem in Chapter 4. Weā™ll also prove a few

technical results on separable endomorphisms. The reader willing to believe

that every endomorphism used in this book is separable, except for powers

of the Frobenius map and multiplication by multiples of p in characteristic p,

can safely omit the technical parts of this section.

By an endomorphism of E, we mean a homomorphism Ī± : E(K) ā’ E(K)

that is given by rational functions. In other words, Ī±(P1 +P2 ) = Ī±(P1 )+Ī±(P2 ),

and there are rational functions (quotients of polynomials) R1 (x, y), R2 (x, y)

with coeļ¬cients in K such that

Ī±(x, y) = (R1 (x, y), R2 (x, y))

for all (x, y) ā E(K). There are a few technicalities when the rational func-

tions are not deļ¬ned at a point. These will be dealt with below. Of course,

since Ī± is a homomorphism, we have Ī±(ā) = ā. We will also assume that

Ī± is nontrivial; that is, there exists some (x, y) such that Ī±(x, y) = ā. The

trivial endomorphism that maps every point to ā will be denoted by 0.

Example 2.4

Let E be given by y 2 = x3 + Ax + B and let Ī±(P ) = 2P . Then Ī± is a

homomorphism and

Ī±(x, y) = (R1 (x, y), R2 (x, y)) ,

where

2

3x2 + A

ā’ 2x

R1 (x, y) =

2y

2

3x2 + A 3x2 + A

3x ā’ ā’ y.

R2 (x, y) =

2y 2y

Since Ī± is a homomorphism given by rational functions it is an endomorphism

of E.

It will be useful to have a standard form for the rational functions describing

an endomorphism. For simplicity, we assume that our elliptic curve is given in

Weierstrass form. Let R(x, y) be any rational function. Since y 2 = x3 +Ax+B

for all (x, y) ā E(K), we can replace any even power of y by a polynomial in

x and replace any odd power of y by y times a polynomial in x and obtain a

Ā© 2008 by Taylor & Francis Group, LLC

51

SECTION 2.9 ENDOMORPHISMS

rational function that gives the same function as R(x, y) on points in E(K).

Therefore, we may assume that

p1 (x) + p2 (x)y

.

R(x, y) =

p3 (x) + p4 (x)y

Moreover, we can rationalize the denominator by multiplying the numerator

and denominator by p3 ā’ p4 y and then replacing y 2 by x3 + Ax + B. This

yields

q1 (x) + q2 (x)y

R(x, y) = . (2.10)

q3 (x)

Consider an endomorphism given by

Ī±(x, y) = (R1 (x, y), R2 (x, y)),

as above. Since Ī± is a homomorphism,

Ī±(x, ā’y) = Ī±(ā’(x, y)) = ā’Ī±(x, y).

This means that

R1 (x, ā’y) = R1 (x, y) R2 (x, ā’y) = ā’R2 (x, y).

and

Therefore, if R1 is written in the form (2.10), then q2 (x) = 0, and if R2 is

written in the form (2.10), then the corresponding q1 (x) = 0. Therefore, we

may assume that

Ī±(x, y) = (r1 (x), r2 (x)y)

with rational functions r1 (x), r2 (x).

We can now say what happens when one of the rational functions is not

deļ¬ned at a point. Write

r1 (x) = p(x)/q(x)

with polynomials p(x) and q(x) that do not have a common factor. If q(x) = 0

for some point (x, y), then we assume that Ī±(x, y) = ā. If q(x) = 0, then

Exercise 2.19 shows that r2 (x) is deļ¬ned; hence the rational functions deļ¬ning

Ī± are deļ¬ned.

We deļ¬ne the degree of Ī± to be

deg(Ī±) = Max{deg p(x), deg q(x)}

if Ī± is nontrivial. When Ī± = 0, let deg(0) = 0. Deļ¬ne Ī± = 0 to be a

separable endomorphism if the derivative r1 (x) is not identically zero. This

is equivalent to saying that at least one of p (x) and q (x) is not identically

zero. See Exercise 2.22. (In characteristic 0, a nonconstant polynomial will

Ā© 2008 by Taylor & Francis Group, LLC

52 CHAPTER 2 THE BASIC THEORY

have nonzero derivative. In characteristic p > 0, the polynomials with zero

derivative are exactly those of the form g(xp ).)

Example 2.5

We continue with the previous example, where Ī±(P ) = 2P . We have

2

3x2 + A

ā’ 2x.

R1 (x, y) =

2y

The fact that y 2 = x3 + Ax + B, plus a little algebraic manipulation, yields

x4 ā’ 2Ax2 ā’ 8Bx + A2

r1 (x) = .

4(x3 + Ax + B)

(This is the same as the expression in terms of division polynomials that will

be given in Section 3.2.) Therefore, deg(Ī±) = 4. The polynomial q (x) =

4(3x2 + A) is not zero (including in characteristic 3, since if A = 0 then

x3 + B has multiple roots, contrary to assumption). Therefore Ī± is separable.

Example 2.6

Letā™s repeat the previous example, but in characteristic 2. Weā™ll use the

formulas from Section 2.8 for doubling a point. First, letā™s look at y 2 + xy =

x3 + a2 x2 + a6 . We have

Ī±(x, y) = (r1 (x), R2 (x, y))

with r1 (x) = (x4 + a6 )/x2 . Therefore deg(Ī±) = 4. Since p (x) = 4x3 = 0 and

q (x) = 2x = 0, the endomorphism Ī± is not separable.

Similarly, in the case y 2 +a3 y = x3 +a4 x+a6 , we have r1 (x) = (x4 +a2 )/a2 .

4 3

Therefore, deg(Ī±) = 4, but Ī± is not separable.

In general, in characteristic p, the map Ī±(Q) = pQ has degree p2 and is not

separable. The statement about the degree is Corollary 3.7. The fact that Ī±

is not separable is proved in Proposition 2.28.

An important example of an endomorphism is the Frobenius map. Sup-

pose E is deļ¬ned over the ļ¬nite ļ¬eld Fq . Let

Ļq (x, y) = (xq , y q ).

The Frobenius map Ļq plays a crucial role in the theory of elliptic curves over

Fq .

LEMMA 2.20

Let E be deļ¬ned over Fq . Then Ļq is an endomorphism of E of degree q,

and Ļq is not separable.

Ā© 2008 by Taylor & Francis Group, LLC

53

SECTION 2.9 ENDOMORPHISMS

PROOF Since Ļq (x, y) = (xq , y q ), the map is given by rational functions

(in fact, by polynomials) and the degree is q. The main point is that Ļq :

E(Fq ) ā’ E(Fq ) is a homomorphism. Let (x1 , y1 ), (x2 , y2 ) ā E(Fq ) with

x1 = x2 . The sum is (x3 , y3 ), with

y 2 ā’ y1

x3 = m2 ā’ x1 ā’ x2 , y3 = m(x1 ā’ x3 ) ā’ y1 , where m =

x2 ā’ x1

(we are working with the Weierstrass form here; the proof for the generalized

Weierstrass form is essentially the same). Raise everything to the qth power

to obtain

q q

y2 ā’ y1

2

xq xq xq , q

(xq xq ) q

=m ā’ ā’ ā’ ā’

y3 =m y1 , where m = q .

3 1 2 1 3

x2 ā’ xq

1

This says that

Ļq (x3 , y3 ) = Ļq (x1 , y1 ) + Ļq (x2 , y2 ).

The cases where x1 = x2 or where one of the points is ā are checked similarly.

However, there is one subtlety that arises when adding a point to itself. The

formula says that 2(x1 , y1 ) = (x3 , y3 ), with

3x2 + A

1

x3 = m2 ā’ 2x1 , y3 = m(x1 ā’ x3 ) ā’ y1 , where m = .

2y1

When this is raised to the qth power, we obtain

3q (xq )2 + Aq

2 1

xq 2xq , q

(xq xq ) q

=m ā’ ā’ ā’

y3 =m y1 , where m = .

3 1 1 3 q

2q y1

Since 2, 3, A ā Fq , we have 2q = 2, 3q = 3, Aq = A. This means that we

obtain the formula for doubling the point (xq , y1 ) on E (if Aq didnā™t equal A,

q

1

we would be working on a new elliptic curve with Aq in place of A).

Since Ļq is a homomorphism given by rational functions, it is an endo-

morphism of E. Since q = 0 in Fq , the derivative of xq is identically zero.

Therefore, Ļq is not separable.

The following result will be crucial in the proof of Hasseā™s theorem in Chap-

ter 4 and in the proof of Theorem 3.2.

PROPOSITION 2.21

Let Ī± = 0 be a separable endomorphism of an elliptic curve E. Then

deg Ī± = #Ker(Ī±),

where Ker(Ī±) is the kernel of the homomorphism Ī± : E(K) ā’ E(K).

If Ī± = 0 is not separable, then

deg Ī± > #Ker(Ī±).

Ā© 2008 by Taylor & Francis Group, LLC

54 CHAPTER 2 THE BASIC THEORY

PROOF Write Ī±(x, y) = (r1 (x), yr2 (x)) with r1 (x) = p(x)/q(x), as above.

Then r1 = 0, so p q ā’ pq is not the zero polynomial.

Let S be the set of x ā K such that (pq ā’p q)(x) q(x) = 0. Let (a, b) ā E(K)

be such that

1. a = 0, b = 0, (a, b) = ā,

2. deg (p(x) ā’ aq(x)) = Max{deg(p), deg(q)} = deg(Ī±),

3. a ā r1 (S), and

4. (a, b) ā Ī±(E(K)).

Since pq ā’p q is not the zero polynomial, S is a ļ¬nite set, hence its image under

Ī± is ļ¬nite. The function r1 (x) is easily seen to take on inļ¬nitely many distinct

values as x runs through K. Since, for each x, there is a point (x, y) ā E(K),

we see that Ī±(E(K)) is an inļ¬nite set. Therefore, such an (a, b) exists.

We claim that there are exactly deg(Ī±) points (x1 , y1 ) ā E(K) such that

Ī±(x1 , y1 ) = (a, b). For such a point, we have

p(x1 )

= a, y1 r2 (x1 ) = b.

q(x1 )

Since (a, b) = ā, we must have q(x1 ) = 0. By Exercise 2.19, r2 (x1 ) is deļ¬ned.

Since b = 0 and y1 r2 (x1 ) = b, we must have y1 = b/r2 (x1 ). Therefore, x1

determines y1 in this case, so we only need to count values of x1 .

By assumption (2), p(x) ā’ aq(x) = 0 has deg(Ī±) roots, counting multiplici-

ties. We therefore must show that p ā’ aq has no multiple roots. Suppose that

x0 is a multiple root. Then

p(x0 ) ā’ aq(x0 ) = 0 p (x0 ) ā’ aq (x0 ) = 0.

and

Multiplying the equations p = aq and aq = p yields

ap(x0 )q (x0 ) = ap (x0 )q(x0 ).

Since a = 0, this implies that x0 is a root of pq ā’ p q, so x0 ā S. Therefore,

a = r1 (x0 ) ā r1 (S), contrary to assumption. It follows that p ā’ aq has no

multiple roots, and therefore has deg(Ī±) distinct roots.

Since there are exactly deg(Ī±) points (x1 , y1 ) with Ī±(x1 , y1 ) = (a, b), the

kernel of Ī± has deg(Ī±) elements.

Of course, since Ī± is a homomorphism, for each (a, b) ā Ī±(E(K)), there are

exactly deg(Ī±) points (x1 , y1 ) with Ī±(x1 , y1 ) = (a, b). The assumptions on

(a, b) were made during the proof to obtain this result for at least one point,

which suļ¬ces.

If Ī± is not separable, then the steps of the above proof hold, except that

p ā’ aq is always the zero polynomial, so p(x) ā’ aq(x) = 0 always has multiple

roots and therefore has fewer than deg(Ī±) solutions.

Ā© 2008 by Taylor & Francis Group, LLC

55

SECTION 2.9 ENDOMORPHISMS

THEOREM 2.22

Let E be an elliptic curve deļ¬ned over a ļ¬eld K. Let Ī± = 0 be an endomor-

phism of E. Then Ī± : E(K) ā’ E(K) is surjective.

REMARK 2.23 We deļ¬nitely need to be working with K instead of K in

the theorem. For example, the Mordell-Weil theorem (Theorem 8.17) implies

that multiplication by 2 cannot be surjective on E(Q) if there is a point in

E(Q) of inļ¬nite order. Intuitively, working with an algebraically closed ļ¬eld

allows us to solve the equations deļ¬ning Ī± in order to ļ¬nd the inverse image

of a point.

PROOF Let (a, b) ā E(K). Since Ī±(ā) = ā, we may assume that

(a, b) = ā. Let r1 (x) = p(x)/q(x) be as above. If p(x) ā’ aq(x) is not a

constant polynomial, then it has a root x0 . Since p and q have no common

roots, q(x0 ) = 0. Choose y0 ā K to be either square root of x3 + Ax0 + B.

0

Then Ī±(x0 , y0 ) is deļ¬ned (Exercise 2.19) and equals (a, b ) for some b . Since

2

b = a3 + Aa + B = b2 , we have b = Ā±b . If b = b, weā™re done. If b = ā’b,

then Ī±(x0 , ā’y0 ) = (a, ā’b ) = (a, b).

We now need to consider the case when p ā’ aq is constant. Since E(K) is

inļ¬nite and the kernel of Ī± is ļ¬nite, only ļ¬nitely many points of E(K) can

map to a point with a given x-coordinate. Therefore, either p(x) or q(x) is not

constant. If p and q are two nonconstant polynomials, then there is at most

one constant a such that p ā’ aq is constant (if a is another such number, then

(a ā’a)q = (pā’aq)ā’(pā’a q) is constant and (a ā’a)p = a (pā’aq)ā’a(pā’a q)

is constant, which implies that p and q are constant). Therefore, there are at

most two points, (a, b) and (a, ā’b) for some b, that are not in the image of

Ī±. Let (a1 , b1 ) be any other point. Then Ī±(P1 ) = (a1 , b1 ) for some P1 . We

can choose (a1 , b1 ) such that (a1 , b1 ) + (a, b) = (a, Ā±b), so there exists P2 with

Ī±(P2 ) = (a1 , b1 ) + (a, b). Then Ī±(P2 ā’ P1 ) = (a, b), and Ī±(P1 ā’ P2 ) = (a, ā’b).

Therefore, Ī± is surjective.

For later applications, we need a convenient criterion for separability. If

(x, y) is a variable point on y 2 = x3 + Ax + B, then we can diļ¬erentiate y

with respect to x:

2yy = 3x2 + A.

Similarly, we can diļ¬erentiate a rational function f (x, y) with respect to x:

d

f (x, y) = fx (x, y) + fy (x, y)y ,

dx

where fx and fy denote the partial derivatives.

Ā© 2008 by Taylor & Francis Group, LLC

56 CHAPTER 2 THE BASIC THEORY

LEMMA 2.24

Let E be the elliptic curve y 2 = x3 + Ax + B. Fix a point (u, v) on E. Write

(x, y) + (u, v) = (f (x, y), g(x, y)),

where f (x, y) and g(x, y) are rational functions of x, y (the coeļ¬cients depend

on (u, v)) and y is regarded as a function of x satisfying dy/dx = (3x2 +

A)/(2y). Then

d

dx f (x, y) 1

=.

g(x, y) y

PROOF The addition formulas give

2

yā’v

ā’xā’u

f (x, y) =

xā’u

ā’(y ā’ v)3 + x(y ā’ v)(x ā’ u)2 + 2u(y ā’ v)(x ā’ u)2 ā’ v(x ā’ u)3

g(x, y) =

(x ā’ u)3

2y (y ā’ v)(x ā’ u) ā’ 2(y ā’ v)2 ā’ (x ā’ u)3

d

f (x, y) = .

(x ā’ u)3

dx

A straightforward but lengthy calculation, using the fact that 2yy = 3x2 + A,

yields

d

(x ā’ u)3 (y f (x, y) ā’ g(x, y))

dx

= v(Au + u3 ā’ v 2 ā’ Ax ā’ x3 + y 2 ) + y(ā’Au ā’ u3 + v 2 + Ax + x3 ā’ y 2 ).

Since (u, v) and (x, y) are on E, we have v 2 = u3 +Au+B and y 2 = x3 +Ax+B.

Therefore, the above expression becomes

v(ā’B + B) + y(B ā’ B) = 0.

d

Therefore, y dx f (x, y) = g(x, y).

REMARK 2.25 Lemma 2.24 is perhaps better stated in terms of diļ¬er-

entials. It says that the diļ¬erential dx/y is translation invariant. In fact, it

is the unique translation invariant diļ¬erential, up to scalar multiples, for E.

See [109].

LEMMA 2.26

Let Ī±1 , Ī±2 , Ī±3 be nonzero endomorphisms of an elliptic curve E with Ī±1 +Ī±2 =

Ī±3 . Write

Ī±j (x, y) = (RĪ±j (x), ySĪ±j (x)).

Ā© 2008 by Taylor & Francis Group, LLC

57

SECTION 2.9 ENDOMORPHISMS

Suppose there are constants cĪ±1 , cĪ±2 such that

RĪ±1 (x) RĪ±2 (x)

= cĪ±1 , = cĪ±2 .

SĪ±1 (x) SĪ±2 (x)

Then

RĪ±3 (x)

= cĪ±1 + cĪ±2 .

SĪ±3 (x)

PROOF Let (x1 , y1 ) and (x2 , y2 ) be variable points on E. Write

(x3 , y3 ) = (x1 , y1 ) + (x2 , y2 ),

where

(x1 , y1 ) = Ī±1 (x, y), (x2 , y2 ) = Ī±2 (x, y).

Then x3 and y3 are rational functions of x1 , y1 , x2 , y2 , which in turn are

rational functions of x, y. By Lemma 2.24, with (u, v) = (x2 , y2 ),

ā‚x3 ā‚x3 dy1 y3

+ =.

ā‚x1 ā‚y1 dx1 y1

Similarly,

ā‚x3 ā‚x3 dy2 y3

+ =.

ā‚x2 ā‚y2 dx2 y2

By assumption,

dxj yj

= cĪ±j

dx y

for j = 1, 2. By the chain rule,

dx3 ā‚x3 dx1 ā‚x3 dy1 dx1 ā‚x3 dx2 ā‚x3 dy2 dx2

= + + +

dx ā‚x1 dx ā‚y1 dx1 dx ā‚x2 dx ā‚y2 dx2 dx

y3 y1 y 3 y2

= cĪ± + cĪ±

y1 y 1 y2 y 2

y3

= (cĪ±1 + cĪ±2 ) .

ńņš. 2 |