<< ńņš. 2(āńåćī 3)ŃĪÄÅŠĘĄĶČÅ >>

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
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

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(āńåćī 3)ŃĪÄÅŠĘĄĶČÅ >>