стр. 1(всего 3)СОДЕРЖАНИЕ >>
Chapter 2
The Basic Theory

2.1 Weierstrass Equations
For most situations in this book, an elliptic curve E is the graph of an
equation of the form
y 2 = x3 + Ax + B,
where A and B are constants. This will be referred to as the Weierstrass
equation for an elliptic curve. We will need to specify what set A, B, x, and
y belong to. Usually, they will be taken to be elements of a п¬Ѓeld, for example,
the real numbers R, the complex numbers C, the rational numbers Q, one of
the п¬Ѓnite п¬Ѓelds Fp (= Zp ) for a prime p, or one of the п¬Ѓnite п¬Ѓelds Fq , where
q = pk with k в‰Ґ 1. In fact, for almost all of this book, the reader who is
not familiar with п¬Ѓelds may assume that a п¬Ѓeld means one of the п¬Ѓelds just
listed. If K is a п¬Ѓeld with A, B в€€ K, then we say that E is deп¬Ѓned over
K. Throughout this book, E and K will implicitly be assumed to denote an
elliptic curve and a п¬Ѓeld over which E is deп¬Ѓned.
If we want to consider points with coordinates in some п¬Ѓeld L вЉ‡ K, we
write E(L). By deп¬Ѓnition, this set always contains the point в€ћ deп¬Ѓned later
in this section:
E(L) = {в€ћ} в€Є (x, y) в€€ L Г— L | y 2 = x3 + Ax + B .
It is not possible to draw meaningful pictures of elliptic curves over most
п¬Ѓelds. However, for intuition, it is useful to think in terms of graphs over the
real numbers. These have two basic forms, depicted in Figure 2.1.
The cubic y 2 = x3 в€’ x in the п¬Ѓrst case has three distinct real roots. In the
second case, the cubic y 2 = x3 + x has only one real root.
What happens if there is a multiple root? We donвЂ™t allow this. Namely, we
assume that
4A3 + 27B 2 = 0.
If the roots of the cubic are r1 , r2 , r3 , then it can be shown that the discrimi-
nant of the cubic is
2
((r1 в€’ r2 )(r1 в€’ r3 )(r2 в€’ r3 )) = в€’(4A3 + 27B 2 ).

9

В© 2008 by Taylor & Francis Group, LLC
10 CHAPTER 2 THE BASIC THEORY

y 2 = x3 в€’ x (b) y 2 = x3 + x
(a)

Figure 2.1

Therefore, the roots of the cubic must be distinct. However, the case where the
roots are not distinct is still interesting and will be discussed in Section 2.10.
In order to have a little more п¬‚exibility, we also allow somewhat more
general equations of the form

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 , (2.1)

where a1 , . . . , a6 are constants. This more general form (weвЂ™ll call it the gen-
eralized Weierstrass equation) is useful when working with п¬Ѓelds of char-
acteristic 2 and characteristic 3. If the characteristic of the п¬Ѓeld is not 2, then
we can divide by 2 and complete the square:

a2 a2
2
a1 x a3 a1 a3
1 3
= x3 + a2 + x2 + a4 +
+ x+ + a6 ,
y+
2 2 4 2 4

which can be written as

y1 = x3 + a2 x2 + a4 x + a6 ,
2

with y1 = y + a1 x/2 + a3 /2 and with some constants a2 , a4 , a6 . If the charac-
teristic is also not 3, then we can let x1 = x + a2 /3 and obtain

y1 = x3 + Ax1 + B,
2
1

for some constants A, B.

В© 2008 by Taylor & Francis Group, LLC
11
SECTION 2.1 WEIERSTRASS EQUATIONS

In most of this book, we will develop the theory using the Weierstrass
equation, occasionally pointing out what modiп¬Ѓcations need to be made in
characteristics 2 and 3. In Section 2.8, we discuss the case of characteristic 2 in
more detail, since the formulas for the (nongeneralized) Weierstrass equation
do not apply. In contrast, these formulas are correct in characteristic 3 for
curves of the form y 2 = x3 + Ax + B, but there are curves that are not of
this form. The general case for characteristic 3 can be obtained by using the
present methods to treat curves of the form y 2 = x3 + Cx2 + Ax + B.

cy 2 = dx3 + ax + b

with c, d = 0. Multiply both sides of the equation by c3 d2 to obtain

(c2 dy)2 = (cdx)3 + (ac2 d)(cdx) + (bc3 d2 ).

The change of variables

y1 = c2 dy, x1 = cdx

yields an equation in Weierstrass form.
Later in this chapter, we will meet other types of equations that can be
transformed into Weierstrass equations for elliptic curves. These will be useful
in certain contexts.
For technical reasons, it is useful to add a point at inп¬Ѓnity to an elliptic
curve. In Section 2.3, this concept will be made rigorous. However, it is
easiest to regard it as a point (в€ћ, в€ћ), usually denoted simply by в€ћ, sitting
at the top of the y-axis. For computational purposes, it will be a formal
symbol satisfying certain computational rules. For example, a line is said to
pass through в€ћ exactly when this line is vertical (i.e., x =constant). The
point в€ћ might seem a little unnatural, but we will see that including it has
very useful consequences.
We now make one more convention regarding в€ћ. It not only is at the top of
the y-axis, it is also at the bottom of the y-axis. Namely, we think of the ends
of the y-axis as wrapping around and meeting (perhaps somewhere in the back
behind the page) in the point в€ћ. This might seem a little strange. However,
if we are working with a п¬Ѓeld other than the real numbers, for example, a
п¬Ѓnite п¬Ѓeld, then there might not be any meaningful ordering of the elements
and therefore distinguishing a top and a bottom of the y-axis might not make
sense. In fact, in this situation, the ends of the y-axis do not have meaning
until we introduce projective coordinates in Section 2.3. This is why it is best
to regard в€ћ as a formal symbol satisfying certain properties. Also, we have
arranged that two vertical lines meet at в€ћ. By symmetry, if they meet at the
top of the y-axis, they should also meet at the bottom. But two lines should
intersect in only one point, so the вЂњtop в€ћвЂќ and the вЂњbottom в€ћвЂќ need to be
the same. In any case, this will be a useful property of в€ћ.

В© 2008 by Taylor & Francis Group, LLC
12 CHAPTER 2 THE BASIC THEORY

2.2 The Group Law
As we saw in Chapter 1, we could start with two points, or even one point,
on an elliptic curve, and produce another point. We now examine this process
in more detail.

PвЂ™
3

P2

P1

P3

Figure 2.2
Adding Points on an Elliptic Curve

P1 = (x1 , y1 ), P2 = (x2 , y2 )
on an elliptic curve E given by the equation y 2 = x3 + Ax + B. Deп¬Ѓne a new
point P3 as follows. Draw the line L through P1 and P2 . WeвЂ™ll see below that
L intersects E in a third point P3 . Reп¬‚ect P3 across the x-axis (i.e., change
the sign of the y-coordinate) to obtain P3 . We deп¬Ѓne
P1 + P2 = P3 .
Examples below will show that this is not the same as adding coordinates of
the points. It might be better to denote this operation by P1 +E P2 , but we
opt for the simpler notation since we will never be adding points by adding
coordinates.
Assume п¬Ѓrst that P1 = P2 and that neither point is в€ћ. Draw the line L
through P1 and P2 . Its slope is
y2 в€’ y 1
m= .
x2 в€’ x1

В© 2008 by Taylor & Francis Group, LLC
13
SECTION 2.2 THE GROUP LAW

If x1 = x2 , then L is vertical. WeвЂ™ll treat this case later, so letвЂ™s assume that
x1 = x2 . The equation of L is then

y = m(x в€’ x1 ) + y1 .

To п¬Ѓnd the intersection with E, substitute to get
2
(m(x в€’ x1 ) + y1 ) = x3 + Ax + B.

This can be rearranged to the form

0 = x3 в€’ m2 x2 + В· В· В· .

The three roots of this cubic correspond to the three points of intersection of
L with E. Generally, solving a cubic is not easy, but in the present case we
already know two of the roots, namely x1 and x2 , since P1 and P2 are points
on both L and E. Therefore, we could factor the cubic to obtain the third
value of x. But there is an easier way. As in Chapter 1, if we have a cubic
polynomial x3 + ax2 + bx + c with roots r, s, t, then

x3 + ax2 + bx + c = (x в€’ r)(x в€’ s)(x в€’ t) = x3 в€’ (r + s + t)x2 + В· В· В· .

Therefore,
r + s + t = в€’a.
If we know two roots r, s, then we can recover the third as t = в€’a в€’ r в€’ s.
In our case, we obtain
x = m2 в€’ x1 в€’ x2
and
y = m(x в€’ x1 ) + y1 .
Now, reп¬‚ect across the x-axis to obtain the point P3 = (x3 , y3 ):

x3 = m2 в€’ x1 в€’ x2 , y3 = m(x1 в€’ x3 ) в€’ y1 .

In the case that x1 = x2 but y1 = y2 , the line through P1 and P2 is a vertical
line, which therefore intersects E in в€ћ. Reп¬‚ecting в€ћ across the x-axis yields
the same point в€ћ (this is why we put в€ћ at both the top and the bottom of
the y-axis). Therefore, in this case P1 + P2 = в€ћ.
Now consider the case where P1 = P2 = (x1 , y1 ). When two points on
a curve are very close to each other, the line through them approximates a
tangent line. Therefore, when the two points coincide, we take the line L
through them to be the tangent line. Implicit diп¬Ђerentiation allows us to п¬Ѓnd
the slope m of L:

3x2 + A
dy
dy
=1
= 3x2 + A, so m= .
2y
dx dx 2y1

В© 2008 by Taylor & Francis Group, LLC
14 CHAPTER 2 THE BASIC THEORY

If y1 = 0 then the line is vertical and we set P1 +P2 = в€ћ, as before. (Technical
point: if y1 = 0, then the numerator 3x2 +A = 0. See Exercise 2.5.) Therefore,
1
assume that y1 = 0. The equation of L is

y = m(x в€’ x1 ) + y1 ,

as before. We obtain the cubic equation

0 = x3 в€’ m2 x2 + В· В· В· .

This time, we know only one root, namely x1 , but it is a double root since L
is tangent to E at P1 . Therefore, proceeding as before, we obtain

x3 = m2 в€’ 2x1 , y3 = m(x1 в€’ x3 ) в€’ y1 .

Finally, suppose P2 = в€ћ. The line through P1 and в€ћ is a vertical line
that intersects E in the point P1 that is the reп¬‚ection of P1 across the x-axis.
When we reп¬‚ect P1 across the x-axis to get P3 = P1 + P2 , we are back at P1 .
Therefore
P1 + в€ћ = P 1
for all points P1 on E. Of course, we extend this to include в€ћ + в€ћ = в€ћ.
LetвЂ™s summarize the above discussion:

GROUP LAW
Let E be an elliptic curve deп¬Ѓned by y 2 = x3 + Ax + B. Let P1 = (x1 , y1 ) and
P2 = (x2 , y2 ) be points on E with P1 , P2 = в€ћ. Deп¬Ѓne P1 + P2 = P3 = (x3 , y3 )
as follows:

1. If x1 = x2 , then
y2 в€’ y 1
x3 = m2 в€’ x1 в€’ x2 , y3 = m(x1 в€’ x3 ) в€’ y1 , where m = .
x2 в€’ x1

2. If x1 = x2 but y1 = y2 , then P1 + P2 = в€ћ.

3. If P1 = P2 and y1 = 0, then

3x2 + A
1
x3 = m2 в€’ 2x1 , y3 = m(x1 в€’ x3 ) в€’ y1 , where m = .
2y1

4. If P1 = P2 and y1 = 0, then P1 + P2 = в€ћ.

Moreover, deп¬Ѓne
P +в€ћ=P
for all points P on E.

В© 2008 by Taylor & Francis Group, LLC
15
SECTION 2.2 THE GROUP LAW

Note that when P1 and P2 have coordinates in a п¬Ѓeld L that contains A and
B, then P1 + P2 also has coordinates in L. Therefore E(L) is closed under
This addition of points might seem a little unnatural. Later (in Chapters 9
and 11), weвЂ™ll interpret it as corresponding to some very natural operations,
but, for the present, letвЂ™s show that it has some nice properties.

THEOREM 2.1
The addition of points on an elliptic curve E satisп¬Ѓes the following properties:
1. (commutativity) P1 + P2 = P2 + P1 for all P1 , P2 on E.
2. (existence of identity) P + в€ћ = P for all points P on E.
3. (existence of inverses) Given P on E, there exists P on E with P +P =
в€ћ. This point P will usually be denoted в€’P .
4. (associativity) (P1 + P2 ) + P3 = P1 + (P2 + P3 ) for all P1 , P2 , P3 on E.
In other words, the points on E form an additive abelian group with в€ћ as the
identity element.

PROOF The commutativity is obvious, either from the formulas or from
the fact that the line through P1 and P2 is the same as the line through P2
and P1 . The identity property of в€ћ holds by deп¬Ѓnition. For inverses, let P
be the reп¬‚ection of P across the x-axis. Then P + P = в€ћ.
Finally, we need to prove associativity. This is by far the most subtle and
nonobvious property of the addition of points on E. It is possible to deп¬Ѓne
many laws of composition satisfying (1), (2), (3) for points on E, either simpler
or more complicated than the one being considered. But it is very unlikely
that such a law will be associative. In fact, it is rather surprising that the
law of composition that we have deп¬Ѓned is associative. After all, we start
with two points P1 and P2 and perform a certain procedure to obtain a third
point P1 + P2 . Then we repeat the procedure with P1 + P2 and P3 to obtain
(P1 + P2 ) + P3 . If we instead start by adding P2 and P3 , then computing
P1 + (P2 + P3 ), there seems to be no obvious reason that this should give the
same point as the other computation.
The associative law can be veriп¬Ѓed by calculation with the formulas. There
are several cases, depending on whether or not P1 = P2 , and whether or not
P3 = (P1 + P2 ), etc., and this makes the proof rather messy. However, we
prefer a diп¬Ђerent approach, which we give in Section 2.4.

Warning: For the Weierstrass equation, if P = (x, y), then в€’P = (x, в€’y).
For the generalized Weierstrass equation (2.1), this is no longer the case. If
P = (x, y) is on the curve described by (2.1), then (see Exercise 2.9)
в€’P = (x, в€’a1 x в€’ a3 в€’ y).

В© 2008 by Taylor & Francis Group, LLC
16 CHAPTER 2 THE BASIC THEORY

Example 2.1
The calculations of Chapter 1 can now be interpreted as adding points on
elliptic curves. On the curve
x(x + 1)(2x + 1)
y2 = ,
6
we have
11 11
(0, 0) + (1, 1) = ( , в€’ ), ( , в€’ ) + (1, 1) = (24, в€’70).
22 22
On the curve
y 2 = x3 в€’ 25x,
we have
1681 62279
,в€’
2(в€’4, 6) = (в€’4, 6) + (в€’4, 6) = .
144 1728
We also have
2(0, 0) = 2(в€’5, 0) = 2(5, 0) = в€ћ.
(0, 0) + (в€’5, 0) = (5, 0),

The fact that the points on an elliptic curve form an abelian group is be-
hind most of the interesting properties and applications. The question arises:
what can we say about the groups of points that we obtain? Here are some
examples.
1. An elliptic curve over a п¬Ѓnite п¬Ѓeld has only п¬Ѓnitely many points with
coordinates in that п¬Ѓnite п¬Ѓeld. Therefore, we obtain a п¬Ѓnite abelian
group in this case. Properties of such groups, and applications to cryp-
tography, will be discussed in later chapters.
2. If E is an elliptic curve deп¬Ѓned over Q, then E(Q) is a п¬Ѓnitely generated
abelian group. This is the Mordell-Weil theorem, which we prove in
Chapter 8. Such a group is isomorphic to Zr вЉ• F for some r в‰Ґ 0
and some п¬Ѓnite group F . The integer r is called the rank of E(Q).
Determining r is fairly diп¬ѓcult in general. It is not known whether r
can be arbitrarily large. At present, there are elliptic curves known with
rank at least 28. The п¬Ѓnite group F is easy to compute using the Lutz-
Nagell theorem of Chapter 8. Moreover, a deep theorem of Mazur says
that there are only п¬Ѓnitely many possibilities for F , as E ranges over all
elliptic curves deп¬Ѓned over Q.
3. An elliptic curve over the complex numbers C is isomorphic to a torus.
This will be proved in Chapter 9. The usual way to obtain a torus is as
C/L, where L is a lattice in C. The usual addition of complex numbers
induces a group law on C/L that corresponds to the group law on the
elliptic curve under the isomorphism between the torus and the elliptic
curve.

В© 2008 by Taylor & Francis Group, LLC
17
SECTION 2.2 THE GROUP LAW

Figure 2.3
An Elliptic Curve over C

4. If E is deп¬Ѓned over R, then E(R) is isomorphic to the unit circle S 1
or to S 1 вЉ• Z2 . The п¬Ѓrst case corresponds to the case where the cubic
polynomial x3 + Ax + B has only one real root (think of the ends of the
graph in Figure 2.1(b) as being hitched together at the point в€ћ to get a
loop). The second case corresponds to the case where the cubic has three
real roots. The closed loop in Figure 2.1(a) is the set S 1 вЉ• {1}, while the
open-ended loop can be closed up using в€ћ to obtain the set S 1 вЉ• {0}.
If we have an elliptic curve E deп¬Ѓned over R, then we can consider its
complex points E(C). These form a torus, as in (3) above. The real
points E(R) are obtained by intersecting the torus with a plane. If the
plane passes through the hole in the middle, we obtain a curve as in
Figure 2.1(a). If it does not pass through the hole, we obtain a curve as
in Figure 2.1(b) (see Section 9.3).
If P is a point on an elliptic curve and k is a positive integer, then kP
denotes P + P + В· В· В· + P (with k summands). If k < 0, then kP = (в€’P ) +
(в€’P ) + В· В· В· (в€’P ), with |k| summands. To compute kP for a large integer k, it
is ineп¬ѓcient to add P to itself repeatedly. It is much faster to use successive
doubling. For example, to compute 19P , we compute

2P, 4P = 2P +2P, 8P = 4P +4P, 16P = 8P +8P, 19P = 16P +2P +P.

This method allows us to compute kP for very large k, say of several hundred
digits, very quickly. The only diп¬ѓculty is that the size of the coordinates of
the points increases very rapidly if we are working over the rational numbers
(see Theorem 8.18). However, when we are working over a п¬Ѓnite п¬Ѓeld, for
example Fp , this is not a problem because we can continually reduce mod p
and thus keep the numbers involved relatively small. Note that the associative

В© 2008 by Taylor & Francis Group, LLC
18 CHAPTER 2 THE BASIC THEORY

law allows us to make these computations without worrying about what order
we use to combine the summands.
The method of successive doubling can be stated in general as follows:

INTEGER TIMES A POINT
Let k be a positive integer and let P be a point on an elliptic curve. The
following procedure computes kP .
1. Start with a = k, B = в€ћ, C = P .
2. If a is even, let a = a/2, and let B = B, C = 2C.
3. If a is odd, let a = a в€’ 1, and let B = B + C, C = C.
4. If a = 0, go to step 2.
5. Output B.
The output B is kP (see Exercise 2.8).

On the other hand, if we are working over a large п¬Ѓnite п¬Ѓeld and are given
points P and kP , it is very diп¬ѓcult to determine the value of k. This is called
the discrete logarithm problem for elliptic curves and is the basis for the
cryptographic applications that will be discussed in Chapter 6.

2.3 Projective Space and the Point at Inп¬Ѓnity
We all know that parallel lines meet at inп¬Ѓnity. Projective space allows us
to make sense out of this statement and also to interpret the point at inп¬Ѓnity
on an elliptic curve.
Let K be a п¬Ѓeld. Two-dimensional projective space P2 over K is given by
K
equivalence classes of triples (x, y, z) with x, y, z в€€ K and at least one of x, y, z
nonzero. Two triples (x1 , y1 , z1 ) and (x2 , y2 , z2 ) are said to be equivalent if
there exists a nonzero element О» в€€ K such that

(x1 , y1 , z1 ) = (О»x2 , О»y2 , О»z2 ).

We write (x1 , y1 , z1 ) в€ј (x2 , y2 , z2 ). The equivalence class of a triple only
depends on the ratios of x to y to z. Therefore, the equivalence class of
(x, y, z) is denoted (x : y : z).
If (x : y : z) is a point with z = 0, then (x : y : z) = (x/z : y/z : 1). These
are the вЂњп¬ЃniteвЂќ points in P2 . However, if z = 0 then dividing by z should
K
be thought of as giving в€ћ in either the x or y coordinate, and therefore the
points (x : y : 0) are called the вЂњpoints at inп¬ЃnityвЂќ in P2 . The point at
K

В© 2008 by Taylor & Francis Group, LLC
19
SECTION 2.3 PROJECTIVE SPACE AND THE POINT AT INFINITY

inп¬Ѓnity on an elliptic curve will soon be identiп¬Ѓed with one of these points at
inп¬Ѓnity in P2 .
K
The two-dimensional aп¬ѓne plane over K is often denoted

A2 = {(x, y) в€€ K Г— K}.
K

We have an inclusion
A2 в†’ P2
K K

given by
(x, y) в†’ (x : y : 1).
In this way, the aп¬ѓne plane is identiп¬Ѓed with the п¬Ѓnite points in P2 . Adding K
the points at inп¬Ѓnity to obtain P2 can be viewed as a way of вЂњcompactifyingвЂќ
K
the plane (see Exercise 2.10).
A polynomial is homogeneous of degree n if it is a sum of terms of the
form axi y j z k with a в€€ K and i + j + k = n. For example, F (x, y, z) =
2x3 в€’ 5xyz + 7yz 2 is homogeneous of degree 3. If a polynomial F is homoge-
neous of degree n then F (О»x, О»y, О»z) = О»n F (x, y, z) for all О» в€€ K. It follows
that if F is homogeneous of some degree, and (x1 , y1 , z1 ) в€ј (x2 , y2 , z2 ), then
F (x1 , y1 , z1 ) = 0 if and only if F (x2 , y2 , z2 ) = 0. Therefore, a zero of F in P2
K
does not depend on the choice of representative for the equivalence class, so
the set of zeros of F in P2 is well deп¬Ѓned.
K
If F (x, y, z) is an arbitrary polynomial in x, y, z, then we cannot talk about
a point in P2 where F (x, y, z) = 0 since this depends on the representative
K
(x, y, z) of the equivalence class. For example, let F (x, y, z) = x2 + 2y в€’ 3z.
Then F (1, 1, 1) = 0, so we might be tempted to say that F vanishes at (1 : 1 :
1). But F (2, 2, 2) = 2 and (1 : 1 : 1) = (2 : 2 : 2). To avoid this problem, we
need to work with homogeneous polynomials.
If f (x, y) is a polynomial in x and y, then we can make it homogeneous by
inserting appropriate powers of z. For example, if f (x, y) = y 2 в€’ x3 в€’ Ax в€’ B,
then we obtain the homogeneous polynomial F (x, y, z) = y 2 z в€’ x3 в€’ Axz 2 в€’
Bz 3 . If F is homogeneous of degree n then
xy
F (x, y, z) = z n f ( , )
zz
and
f (x, y) = F (x, y, 1).
We can now see what it means for two parallel lines to meet at inп¬Ѓnity. Let

y = mx + b1 , y = mx + b2

be two nonvertical parallel lines with b1 = b2 . They have the homogeneous
forms
y = mx + b1 z, y = mx + b2 z.

В© 2008 by Taylor & Francis Group, LLC
20 CHAPTER 2 THE BASIC THEORY

(The preceding discussion considered only equations of the form f (x, y) = 0
and F (x, y, z) = 0; however, there is nothing wrong with rearranging these
equations to the form вЂњhomogeneous of degree n = homogeneous of degree
n.вЂќ) When we solve the simultaneous equations to п¬Ѓnd their intersection, we
obtain
z = 0 and y = mx.
Since we cannot have all of x, y, z being 0, we must have x = 0. Therefore, we
can rescale by dividing by x and п¬Ѓnd that the intersection of the two lines is

(x : mx : 0) = (1 : m : 0).

Similarly, if x = c1 and x = c2 are two vertical lines, they intersect in the
point (0 : 1 : 0). This is one of the points at inп¬Ѓnity in P2 .
K
Now letвЂ™s look at the elliptic curve E given by y 2 = x3 + Ax + B. Its
homogeneous form is y 2 z = x3 + Axz 2 + Bz 3 . The points (x, y) on the
original curve correspond to the points (x : y : 1) in the projective version. To
see what points on E lie at inп¬Ѓnity, set z = 0 and obtain 0 = x3 . Therefore
x = 0, and y can be any nonzero number (recall that (0 : 0 : 0) is not allowed).
Rescale by y to п¬Ѓnd that (0 : y : 0) = (0 : 1 : 0) is the only point at inп¬Ѓnity on
E. As we saw above, (0 : 1 : 0) lies on every vertical line, so every vertical line
intersects E at this point at inп¬Ѓnity. Moreover, since (0 : 1 : 0) = (0 : в€’1 : 0),
the вЂњtopвЂќ and the вЂњbottomвЂќ of the y-axis are the same.
There are situations where using projective coordinates speeds up compu-
tations on elliptic curves (see Section 2.6). However, in this book we almost
always work in aп¬ѓne (nonprojective) coordinates and treat the point at inп¬Ѓn-
ity as a special case when needed. An exception is the proof of associativity
of the group law given in Section 2.4, where it will be convenient to have the
point at inп¬Ѓnity treated like any other point (x : y : z).

2.4 Proof of Associativity
In this section, we prove the associativity of addition of points on an elliptic
curve. The reader who is willing to believe this result may skip this section
without missing anything that is needed in the rest of the book. However,
as corollaries of the proof, we will obtain two results, namely the theorems of
Pappus and Pascal, that are not about elliptic curves but which are interesting
in their own right.
The basic idea is the following. Start with an elliptic curve E and points
P, Q, R on E. To compute в€’ ((P + Q) + R) we need to form the lines 1 =
P Q, m2 = в€ћ, P + Q, and 3 = R, P + Q, and see where they intersect E.
To compute в€’ ((P + (Q + R)) we need to form the lines m1 = QR, 2 =
в€ћ, Q + R, and m3 = P, Q + R. It is easy to see that the points Pij = i в€© mj

В© 2008 by Taylor & Francis Group, LLC
21
SECTION 2.4 PROOF OF ASSOCIATIVITY

lie on E, except possibly for P33 . We show in Theorem 2.6 that having the
eight points Pij = P33 on E forces P33 to be on E. Since 3 intersects E at
the points R, P + Q, в€’ ((P + Q) + R), we must have в€’ ((P + Q) + R) = P33 .
Similarly, в€’ (P + (Q + R)) = P33 , so

в€’ ((P + Q) + R) = в€’ (P + (Q + R)) ,

which implies the desired associativity.
There are three main technicalities that must be treated. First, some of
the points Pij could be at inп¬Ѓnity, so we need to use projective coordinates.
Second, a line could be tangent to E, which means that two Pij could be
equal. Therefore, we need a careful deп¬Ѓnition of the order to which a line
intersects a curve. Third, two of the lines could be equal. Dealing with these
technicalities takes up most of our attention during the proof.
First, we need to discuss lines in P2 . The standard way to describe a line
K
is by a linear equation: ax + by + cz = 0. Sometimes it is useful to give a
parametric description:

x = a1 u + b1 v
y = a2 u + b2 v (2.2)
z = a3 u + b3 v

where u, v run through K, and at least one of u, v is nonzero. For example, if
a = 0, the line
ax + by + cz = 0
can be described by

x = в€’(b/a)u в€’ (c/a)v, y = u, z = v.

Suppose all the vectors (ai , bi ) are multiples of each other, say (ai , bi ) =
О»i (a1 , b1 ). Then (x, y, z) = x(1, О»2 , О»3 ) for all u, v such that x = 0. So we get
a point, rather than a line, in projective space. Therefore, we need a condition
on the coeп¬ѓcients a1 , . . . , b3 that ensure that we actually get a line. It is not
hard to see that we must require the matrix
вЋ› вЋћ
a1 b1
вЋќ a2 b2 вЋ
a3 b3

to have rank 2 (cf. Exercise 2.12).
If (u1 , v1 ) = О»(u2 , v2 ) for some О» в€€ K Г— , then (u1 , v1 ) and (u2 , v2 ) yield
equivalent triples (x, y, z). Therefore, we can regard (u, v) as running through
points (u : v) in 1-dimensional projective space P1 . Consequently, a line
K
corresponds to a copy of the projective line P1 embedded in the projective
K
plane.

В© 2008 by Taylor & Francis Group, LLC
22 CHAPTER 2 THE BASIC THEORY

We need to quantify the order to which a line intersects a curve at a point.
The following gets us started.

LEMMA 2.2
Let G(u, v) be a nonzero homogeneous polynomial and let (u0 : v0 ) в€€ P1 . K
Then there exists an integer k в‰Ґ 0 and a polynomial H(u, v) with H(u0 , v0 ) =
0 such that
G(u, v) = (v0 u в€’ u0 v)k H(u, v).

PROOF Suppose v0 = 0. Let m be the degree of G. Let g(u) = G(u, v0 ).
By factoring out as large a power of u в€’ u0 as possible, we can write g(u) =
(u в€’ u0 )k h(u) for some k and for some polynomial h of degree m в€’ k with
h(u0 ) = 0. Let H(u, v) = (v mв€’k /v0 )h(uv0 /v), so H(u, v) is homogeneous of
m

degree m в€’ k. Then
m
v mв€’k
uv0 uv0
v k
= m (v0 u в€’ u0 v) h
g
G(u, v) =
v0 v v0 v
=(v0 u в€’ u0 v)k H(u, v),
as desired.
If v0 = 0, then u0 = 0. Reversing the roles of u and v yields the proof in
this case.

Let f (x, y) = 0 (where f is a polynomial) describe a curve C in the aп¬ѓne
plane and let
x = a1 t + b1 , y = a2 t + b2
be a line L written in terms of the parameter t. Let
Лњ
f (t) = f (a1 t + b1 , a2 t + b2 ).
Then L intersects C when t = t0 if f (t0 ) = 0. If (t в€’ t0 )2 divides f (t),
Лњ Лњ
then L is tangent to C (if the point corresponding to t0 is nonsingular. See
Lemma 2.5). More generally, we say that L intersects C to order n at the
point (x, y) corresponding to t = t0 if (t в€’ t0 )n is the highest power of (t в€’ t0 )
Лњ
that divides f (t).
The homogeneous version of the above is the following. Let F (x, y, z) be a
homogeneous polynomial, so F = 0 describes a curve C in P2 . Let L be a
K
line given parametrically by (2.2) and let
Лњ
F (u, v) = F (a1 u + b1 v, a2 u + b2 v, a3 u + b3 v).
We say that L intersects C to order n at the point P = (x0 : y0 : z0 )
corresponding to (u : v) = (u0 : v0 ) if (v0 u в€’ u0 v)n is the highest power of
Лњ
(v0 u в€’ u0 v) dividing F (u, v). We denote this by
ordL,P (F ) = n.

В© 2008 by Taylor & Francis Group, LLC
23
SECTION 2.4 PROOF OF ASSOCIATIVITY

Лњ
If F is identically 0, then we let ordL,P (F ) = в€ћ. It is not hard to show that
ordL,P (F ) is independent of the choice of parameterization of the line L. Note
that v = v0 = 1 corresponds to the nonhomogeneous situation above, and the
deп¬Ѓnitions coincide (at least when z = 0). The advantage of the homogeneous
formulation is that it allows us to treat the points at inп¬Ѓnity along with the
п¬Ѓnite points in a uniform manner.

LEMMA 2.3
Let L1 and L2 be lines intersecting in a point P , and, for i = 1, 2, let
Li (x, y, z) be a linear polynomial deп¬Ѓning Li . Then ordL1 ,P (L2 ) = 1 unless
L1 (x, y, z) = О±L2 (x, y, z) for some constant О±, in which case ordL1 ,P (L2 ) =
в€ћ.

PROOF When we substitute the parameterization for L1 into L2 (x, y, z),
Лњ
we obtain L2 , which is a linear expression in u, v. Let P correspond to (u0 :
Лњ Лњ
v0 ). Since L2 (u0 , v0 ) = 0, it follows that L2 (u, v) = ОІ(v0 u в€’ u0 v) for some
constant ОІ. If ОІ = 0, then ordL1 ,P (L2 ) = 1. If ОІ = 0, then all points on
L1 lie on L2 . Since two points in P2 determine a line, and L1 has at least
K
1
three points (PK always contains the points (1 : 0), (0 : 1), (1 : 1)), it follows
that L1 and L2 are the same line. Therefore L1 (x, y, z) is proportional to
L2 (x, y, z).

Usually, a line that intersects a curve to order at least 2 is tangent to the
curve. However, consider the curve C deп¬Ѓned by

F (x, y, z) = y 2 z в€’ x3 = 0.

Let
x = au, y = bu, z=v
be a line through the point P = (0 : 0 : 1). Note that P corresponds to
(u : v) = (0 : 1). We have F (u, v) = u2 (b2 v в€’ a3 u), so every line through P
Лњ
intersects C to order at least 2. The line with b = 0, which is the best choice
for the tangent at P , intersects C to order 3. The aп¬ѓne part of C is the curve
y 2 = x3 , which is pictured in Figure 2.7. The point (0, 0) is a singularity of
the curve, which is why the intersections at P have higher orders than might
be expected. This is a situation we usually want to avoid.

DEFINITION 2.4 A curve C in P2 deп¬Ѓned by F (x, y, z) = 0 is said to be
K
nonsingular at a point P if at least one of the partial derivatives Fx , Fy , Fz
is nonzero at P .

For example, consider an elliptic curve deп¬Ѓned by F (x, y, z) = y 2 z в€’ x3 в€’
Axz 2 в€’ Bz 3 = 0, and assume the characteristic of our п¬Ѓeld K is not 2 or 3.

В© 2008 by Taylor & Francis Group, LLC
24 CHAPTER 2 THE BASIC THEORY

We have
Fx = в€’3x2 в€’ Az 2 , Fz = y 2 в€’ 2Axz в€’ 3Bz 2 .
Fy = 2yz,
Suppose P = (x : y : z) is a singular point. If z = 0, then Fx = 0 implies
x = 0 and Fz = 0 implies y = 0, so P = (0 : 0 : 0), which is impossible.
Therefore z = 0, so we may take z = 1 (and therefore ignore it). If Fy = 0,
then y = 0. Since (x : y : 1) lies on the curve, x must satisfy x3 + Ax + B = 0.
If Fx = в€’(3x2 + A) = 0, then x is a root of a polynomial and a root of its
derivative, hence a double root. Since we assumed that the cubic polynomial
has no multiple roots, we have a contradiction. Therefore an elliptic curve has
no singular points. Note that this is true even if we are considering points with
coordinates in K (= algebraic closure of K). In general, by a nonsingular
curve we mean a curve with no singular points in K.
If we allow the cubic polynomial to have a multiple root x, then it is easy to
see that the curve has a singularity at (x : 0 : 1). This case will be discussed
in Section 2.10.
If P is a nonsingular point of a curve F (x, y, z) = 0, then the tangent line
at P is
Fx (P )x + Fy (P )y + Fz (P )z = 0.
For example, if F (x, y, z) = y 2 z в€’ x3 в€’ Axz 2 в€’ Bz 3 = 0, then the tangent
line at (x0 : y0 : z0 ) is
(в€’3x2 в€’ Az0 )x + 2y0 z0 y + (y0 в€’ 2Ax0 z0 в€’ 3Bz0 )z = 0.
2 2 2
0

If we set z0 = z = 1, then we obtain
(в€’3x2 в€’ A)x + 2y0 y + (y0 в€’ 2Ax0 в€’ 3B) = 0.
2
0

Using the fact that y0 = x3 + Ax0 + B, we can rewrite this as
2
0

(в€’3x2 в€’ A)(x в€’ x0 ) + 2y0 (y в€’ y0 ) = 0.
0

This is the tangent line in aп¬ѓne coordinates that we used in obtaining the
formulas for adding a point to itself on an elliptic curve. Now letвЂ™s look at
the point at inп¬Ѓnity on this curve. We have (x0 : y0 : z0 ) = (0 : 1 : 0). The
tangent line is given by 0x + 0y + z = 0, which is the вЂњline at inп¬ЃnityвЂќ in P2 .
K
It intersects the elliptic curve only in the point (0 : 1 : 0). This corresponds
to the fact that в€ћ + в€ћ = в€ћ on an elliptic curve.

LEMMA 2.5
Let F (x, y, z) = 0 deп¬Ѓne a curve C. If P is a nonsingular point of C, then
there is exactly one line in P2 that intersects C to order at least 2, and it is
K
the tangent to C at P .

PROOF Let L be a line intersecting C to order k в‰Ґ 1. Parameterize L
Лњ
by (2.2) and substitute into F . This yields F (u, v). Let (u0 : v0 ) correspond

В© 2008 by Taylor & Francis Group, LLC
25
SECTION 2.4 PROOF OF ASSOCIATIVITY

Лњ
to P . Then F = (v0 u в€’ u0 v)k H(u, v) for some H(u, v) with H(u0 , v0 ) = 0.
Therefore,
Лњ
Fu (u, v) = kv0 (v0 u в€’ u0 v)kв€’1 H(u, v) + (v0 u в€’ u0 v)k Hu (u, v)

and
Лњ
Fv (u, v) = в€’ku0 (v0 u в€’ u0 v)kв€’1 H(u, v) + (v0 u в€’ u0 v)k Hv (u, v).
Лњ Лњ
It follows that k в‰Ґ 2 if and only if Fu (u0 , v0 ) = Fv (u0 , v0 ) = 0.
Suppose k в‰Ґ 2. The chain rule yields
Лњ Лњ
Fu = a1 Fx + a2 Fy + a3 Fz = 0, F v = b 1 F x + b2 F y + b3 F z = 0 (2.3)

at P . Recall that since the parameterization (2.2) yields a line, the vectors
(a1 , a2 , a3 ) and (b1 , b2 , b3 ) must be linearly independent.
Suppose L is another line that intersects C to order at least 2. Then we
obtain another set of equations

a1 Fx + a2 Fy + a3 Fz = 0, b1 Fx + b2 Fy + b3 Fz = 0

at P .
If the vectors a = (a1 , a2 , a3 ) and b = (b1 , b2 , b3 ) span the same plane in
3
K as a = (a1 , a2 , a3 ) and b = (b1 , b2 , b3 ), then

a = О±a + ОІb, b = Оіa + Оґb
О±ОІ
for some invertible matrix . Therefore,
ОіОґ

ua + vb = (uО± + vОі)a + (uОІ + vОґ)b = u1 a + v1 b

for a new choice of parameters u1 , v1 . This means that L and L are the same
line.
If L and L are diп¬Ђerent lines, then a, b and a , b span diп¬Ђerent planes, so
the vectors a, b, a , b must span all of K 3 . Since (Fx , Fy , Fz ) has dot product
0 with these vectors, it must be the 0 vector. This means that P is a singular
point, contrary to our assumption.
Finally, we need to show that the tangent line intersects the curve to order
at least 2. Suppose, for example, that Fx = 0 at P . The cases where Fy = 0
and Fz = 0 are similar. The tangent line can be given the parameterization

x = в€’(Fy /Fx )u в€’ (Fz /Fx )v, y = u, z = v,

so
a1 = в€’Fy /Fx , b1 = в€’Fz /Fx , a2 = 1, b2 = 0, a3 = 0, b3 = 1
in the notation of (2.2). Substitute into (2.3) to obtain
Лњ Лњ
Fu = (в€’Fy /Fx )Fx + Fy = 0, Fv = (в€’Fz /Fx )Fx + Fz = 0.

В© 2008 by Taylor & Francis Group, LLC
26 CHAPTER 2 THE BASIC THEORY

By the discussion at the beginning of the proof, this means that the tangent
line intersects the curve to order k в‰Ґ 2.

The associativity of elliptic curve addition will follow easily from the next
result. The proof can be simpliп¬Ѓed if the points Pij are assumed to be distinct.
The cases where points are equal correspond to situations where tangent lines
are used in the deп¬Ѓnition of the group law. Correspondingly, this is where
it is more diп¬ѓcult to verify the associativity by direct calculation with the
formulas for the group law.

THEOREM 2.6
Let C(x, y, z) be a homogeneous cubic polynomial, and let C be the curve in
P2 described by C(x, y, z) = 0. Let 1 , 2 , 3 and m1 , m2 , m3 be lines in P2
K K
such that i = mj for all i, j. Let Pij be the point of intersection of i and
mj . Suppose Pij is a nonsingular point on the curve C for all (i, j) = (3, 3).
In addition, we require that if, for some i, there are k в‰Ґ 2 of the points
Pi1 , Pi2 , Pi3 equal to the same point, then i intersects C to order at least k
at this point. Also, if, for some j, there are k в‰Ґ 2 of the points P1j , P2j , P3j
equal to the same point, then mj intersects C to order at least k at this point.
Then P33 also lies on the curve C.

PROOF Express 1 in the parametric form (2.2). Then C(x, y, z) becomes
Лњ
C(u, v). The line 1 passes through P11 , P12 , P13 . Let (u1 : v1 ), (u2 : v2 ), (u3 :
v3 ) be the parameters on 1 for these points. Since these points lie on C, we
Лњ
have C(ui , vi ) = 0 for i = 1, 2, 3.
Let mj have equation mj (x, y, z) = aj x + bj y + cj z = 0. Substituting
the parameterization for 1 yields mj (u, v). Since Pij lies on mj , we have
Лњ
mj (uj , vj ) = 0 for j = 1, 2, 3. Since 1 = mj and since the zeros of mj yield the
Лњ Лњ
intersections of 1 and mj , the function mj (u, v) vanishes only at P1j , so the
Лњ
linear form mj is nonzero. Therefore, the product m1 (u, v)m2 (u, v)m3 (u, v)
Лњ Лњ Лњ Лњ
is a nonzero cubic homogeneous polynomial. We need to relate this product
Лњ
to C.

LEMMA 2.7
Let R(u, v) and S(u, v) be homogeneous polynomials of degree 3, with S(u, v)
not identically 0, and suppose there are three points (ui : vi ), i = 1, 2, 3, at
which R and S vanish. Moreover, if k of these points are equal to the same
point, we require that R and S vanish to order at least k at this point (that
is, (vi u в€’ ui v)k divides R and S). Then there is a constant О± в€€ K such that
R = О±S.

PROOF First, observe that a nonzero cubic homogeneous polynomial
S(u, v) can have at most 3 zeros (u : v) in P1 (counting multiplicities).
K

В© 2008 by Taylor & Francis Group, LLC
27
SECTION 2.4 PROOF OF ASSOCIATIVITY

This can be proved as follows. Factor oп¬Ђ the highest possible power of v, say
v k . Then S(u, v) vanishes to order k at (1 : 0), and S(u, v) = v k S0 (u, v) with
S0 (1, 0) = 0. Since S0 (u, 1) is a polynomial of degree 3 в€’ k, the polynomial
S0 (u, 1) can have at most 3 в€’ k zeros, counting multiplicities (it has exactly
3 в€’ k if K is algebraically closed). All points (u : v) = (1 : 0) can be written
in the form (u : 1), so S0 (u, v) has at most 3 в€’ k zeros. Therefore, S(u, v) has
at most k + (3 в€’ k) = 3 zeros in P1 . K
It follows easily that the condition that S(u, v) vanish to order at least k
could be replaced by the condition that S(u, v) vanish to order exactly k.
However, it is easier to check вЂњat leastвЂќ than вЂњexactly.вЂќ Since we are allowing
the possibility that R(u, v) is identically 0, this remark does not apply to R.
Let (u0 , : v0 ) be any point in P1 not equal to any of the (ui : vi ). (Technical
K
point: If K has only two elements, then P1 has only three elements. In this
K
case, enlarge K to GF (4). The О± we obtain is forced to be in K since it is the
ratio of a coeп¬ѓcient of R and a coeп¬ѓcient of S, both of which are in K.) Since
S can have at most three zeros, S(u0 , v0 ) = 0. Let О± = R(u0 , v0 )/S(u0 , v0 ).
Then R(u, v) в€’ О±S(u, v) is a cubic homogeneous polynomial that vanishes at
the four points (ui : vi ), i = 0, 1, 2, 3. Therefore R в€’ О±S must be identically
zero.

Лњ
Returning to the proof of the theorem, we note that C and m1 m2 m3 vanish
ЛњЛњЛњ
at the points (ui : vi ), i = 1, 2, 3. Moreover, if k of the points P1j are the
same point, then k of the linear functions vanish at this point, so the product
Лњ
m1 (u, v)m2 (u, v)m3 (u, v) vanishes to order at least k. By assumption, C
Лњ Лњ Лњ
vanishes to order at least k in this situation. By the lemma, there exists a
constant О± such that
Лњ
C = О± m1 m 2 m 3 .
ЛњЛњЛњ
Let
C1 (x, y, z) = C(x, y, z) в€’ О±m1 (x, y, z)m2 (x, y, z)m3 (x, y, z).
The line 1 can be described by a linear equation 1 (x, y, z) = ax+by +cz =
0. At least one coeп¬ѓcient is nonzero, so letвЂ™s assume a = 0. The other cases
are similar. The parameterization of the line 1 can be taken to be

x = в€’(b/a)u в€’ (c/a)v, y = u, z = v. (2.4)

Лњ
Then C1 (u, v) = C1 (в€’(b/a)u в€’ (c/a)v, u, v). Write C1 (x, y, z) as a polynomial
in x with polynomials in y, z as coeп¬ѓcients. Writing
n
xn = (1/an ) ((ax + by + cz) в€’ (by + cz)) = (1/an ) ((ax + by + cz)n + В· В· В· ) ,

we can rearrange C1 (x, y, z) to be a polynomial in ax + by + cz whose coeп¬ѓ-
cients are polynomials in y, z:

C1 (x, y, z) = a3 (y, z)(ax + by + cz)3 + В· В· В· + a0 (y, z). (2.5)

В© 2008 by Taylor & Francis Group, LLC
28 CHAPTER 2 THE BASIC THEORY

Substituting (2.4) into (2.5) yields
Лњ
0 = C1 (u, v) = a0 (u, v),
since ax + by + cz vanishes identically when x, y, z are written in terms of u, v.
Therefore a0 (y, z) = a0 (u, v) is the zero polynomial. It follows from (2.5) that
C1 (x, y, z) is a multiple of 1 (x, y, z) = ax + by + cz.
Similarly, there exists a constant ОІ such that C(x, y, z) в€’ ОІ 1 2 3 is a mul-
tiple of m1 .
Let
D(x, y, z) = C в€’ О±m1 m2 m3 в€’ ОІ 1 2 3.

Then D(x, y, z) is a multiple of and a multiple of m1 .
1

LEMMA 2.8
D(x, y, z) is a multiple of 1 (x, y, z)m1 (x, y, z).

PROOF Write D = m1 D1 . We need to show that 1 divides D1 . We
as follows. Parameterize the line 1 via (2.4) (again, we are considering the
Лњ ЛњЛњ
case a = 0). Substituting this into the relation D = m1 D1 yields D = m1 D1 .
Лњ
Since 1 divides D, we have D = 0. Since m1 = 1 , we have m1 = 0. Therefore
Лњ
Лњ 1 (u, v) is the zero polynomial. As above, this implies that D1 (x, y, z) is a
D
multiple of 1 , as desired.

By the lemma,
D(x, y, z) = 1 m1 ,
where (x, y, z) is linear. By assumption, C = 0 at P22 , P23 , P32 . Also, 1 2 3
and m1 m2 m3 vanish at these points. Therefore, D(x, y, z) vanishes at these
points. Our goal is to show that D is identically 0.

LEMMA 2.9
(P22 ) = (P23 ) = (P32 ) = 0.

PROOF First suppose that P13 = P23 . If 1 (P23 ) = 0, then P23 is on
the line 1 and also on 2 and m3 by deп¬Ѓnition. Therefore, P23 equals the
intersection P13 of 1 and m3 . Since P23 and P13 are for the moment assumed
to be distinct, this is a contradiction. Therefore 1 (P23 ) = 0. Since D(P23 ) =
0, it follows that m1 (P23 ) (P23 ) = 0.
Suppose now that P13 = P23 . Then, by the assumption in the theo-
rem, m3 is tangent to C at P23 , so ordm3 ,P23 (C) в‰Ґ 2. Since P13 = P23
and P23 lies on m3 , we have ordm3 ,P23 ( 1 ) = ordm3 ,P23 ( 2 ) = 1. There-
fore, ordm3 ,P23 (О± 1 2 3 ) в‰Ґ 2. Also, ordm3 ,P23 (ОІm1 m2 m3 ) = в€ћ. Therefore,

В© 2008 by Taylor & Francis Group, LLC
29
SECTION 2.4 PROOF OF ASSOCIATIVITY

ordm3 ,P23 (D) в‰Ґ 2, since D is a sum of terms, each of which vanishes to order
at least 2. But ordm3 ,P23 ( 1 ) = 1, so we have

ordm3 ,P23 (m1 ) = ordm3 ,P23 (D) в€’ ordm3 ,P23 ( 1 ) в‰Ґ 1.

Therefore m1 (P23 ) (P23 ) = 0.
In both cases, we have m1 (P23 ) (P23 ) = 0.
If m1 (P23 ) = 0, then (P23 ) = 0, as desired.
If m1 (P23 ) = 0, then P23 lies on m1 , and also on 2 and m3 , by deп¬Ѓnition.
Therefore, P23 = P21 , since 2 and m1 intersect in a unique point. By as-
sumption, 2 is therefore tangent to C at P23 . Therefore, ord 2 ,P23 (C) в‰Ґ 2.
As above, ord 2 ,P23 (D) в‰Ґ 2, so

) в‰Ґ 1.
ord ( 1
2 ,P23

If in this case we have 1 (P23 ) = 0, then P23 lies on 1 , 2 , m3 . Therefore
P13 = P23 . By assumption, the line m3 is tangent to C at P23 . Since P23 is a
nonsingular point of C, Lemma 2.5 says that 2 = m3 , contrary to hypothesis.
Therefore, 1 (P23 ) = 0, so (P23 ) = 0.
Similarly, (P22 ) = (P32 ) = 0.

If (x, y, z) is identically 0, then D is identically 0. Therefore, assume that
(x, y, z) is not zero and hence it deп¬Ѓnes a line .
First suppose that P23 , P22 , P32 are distinct. Then and 2 are lines through
P23 and P22 . Therefore = 2 . Similarly, = m2 . Therefore 2 = m2 ,
Now suppose that P32 = P22 . Then m2 is tangent to C at P22 . As before,

ordm2 ,P22 ( 1 m1 ) в‰Ґ 2.

We want to show that this forces to be the same line as m2 .
If m1 (P22 ) = 0, then P22 lies on m1 , m2 , 2 . Therefore, P21 = P22 . This
means that 2 is tangent to C at P22 . By Lemma 2.5, 2 = m2 , contradiction.
Therefore, m1 (P22 ) = 0.
If 1 (P22 ) = 0, then ordm2 ,P22 ( ) в‰Ґ 2. This means that is the same line as
m2 .
If 1 (P22 ) = 0, then P22 = P32 lies on 1 , 2 , 3 , m2 , so P12 = P22 =
P32 . Therefore ordm2 ,P22 (C) в‰Ґ 3. By the reasoning above, we now have
ordm2 ,P22 ( 1 m1 ) в‰Ґ 3. Since we have proved that m1 (P22 ) = 0, we have
ordm2 ,P22 ( ) в‰Ґ 2. This means that is the same line as m2 .
So now we have proved, under the assumption that P32 = P22 , that is the
same line as m2 . By Lemma 2.9, P23 lies on , and therefore on m2 . It also
lies on 2 and m3 . Therefore, P22 = P23 . This means that 2 is tangent to C
at P22 . Since P32 = P22 means that m2 is also tangent to C at P22 , we have
2 = m2 , contradiction. Therefore, P32 = P22 (under the assumption that
= 0).

В© 2008 by Taylor & Francis Group, LLC
30 CHAPTER 2 THE BASIC THEORY

Similarly, P23 = P22 .
Finally, suppose P23 = P32 . Then P23 lies on 2 , 3 , m2 , m3 . This forces
P22 = P32 , which we have just shown is impossible.
Therefore, all possibilities lead to contradictions. It follows that (x, y, z)
must be identically 0. Therefore D = 0, so

C=О± + ОІm1 m2 m3 .
123

Since 3 and m3 vanish at P33 , we have C(P33 ) = 0, as desired. This completes
the proof of Theorem 2.6.

REMARK 2.10 Note that we proved the stronger result that

C=О± + ОІm1 m2 m3
123

for some constants О±, ОІ. Since there are 10 coeп¬ѓcients in an arbitrary ho-
mogeneous cubic polynomial in three variables and we have required that C
vanish at eight points (when the Pij are distinct), it is not surprising that the
set of possible polynomials is a two-parameter family. When the Pij are not
distinct, the tangency conditions add enough restrictions that we still obtain
a two-parameter family.

We can now prove the associativity of addition for an elliptic curve. Let
P, Q, R be points on E. Deп¬Ѓne the lines

= в€ћ, Q + R,
= P Q, = R, P + Q
1 2 3

m2 = в€ћ, P + Q,
m1 = QR, m3 = P, Q + R.
We have the following intersections:

1 2 3
в€’(Q + R)
m1 Q R
в€’(P + Q) в€ћ
m2 P +Q
m3 P Q+R X

Assume for the moment that the hypotheses of the theorem are satisп¬Ѓed.
Then all the points in the table, including X, lie on E. The line 3 has three
points of intersection with E, namely R, P + Q, and X. By the deп¬Ѓnition of
addition, X = в€’((P + Q) + R). Similarly, m3 intersects C in 3 points, which
means that X = в€’(P + (Q + R)). Therefore, after reп¬‚ecting across the x-axis,
we obtain (P + Q) + R = P + (Q + R), as desired.
It remains to verify the hypotheses of the theorem, namely that the orders
of intersection are correct and that the lines i are distinct from the lines mj .
First we want to dispense with cases where в€ћ occurs. The problem is that
we treated в€ћ as a special case in the deп¬Ѓnition of the group law. However,

В© 2008 by Taylor & Francis Group, LLC
31
SECTION 2.4 PROOF OF ASSOCIATIVITY

as pointed out earlier, the tangent line at в€ћ intersects the curve only at в€ћ
(and intersects to order 3 at в€ћ). It follows that if two of the entries in a row
or column of the above table of intersections are equal to в€ћ, then so is the
third, and the line intersects the curve to order 3. Therefore, this hypothesis
is satisп¬Ѓed.
It is also possible to treat directly the cases where some of the intersection
points P, Q, R, В±(P + Q), В±(Q + R) are в€ћ. In the cases where at least one of
P, Q, R is в€ћ, associativity is trivial.
If P + Q = в€ћ, then (P + Q) + R = в€ћ + R = R. On the other hand,
the sum Q + R is computed by п¬Ѓrst drawing the line L through Q and R,
which intersects E in в€’(Q + R). Since P + Q = в€ћ, the reп¬‚ection of Q across
the x-axis is P . Therefore, the reп¬‚ection L of L passes through P , в€’R, and
Q + R. The sum P + (Q + R) is found by drawing the line through P and
Q + R, which is L . We have just observed that the third point of intersection
of L with E is в€’R. Reп¬‚ecting yields P + (Q + R) = R, so associativity holds
in this case.
Similarly, associativity holds when Q + R = в€ћ.
Finally, we need to consider what happens if some line i equals some line
mj , since then Theorem 2.6 does not apply.
First, observe that if P, Q, R are collinear, then associativity is easily veriп¬Ѓed
directly.
Second, suppose that P, Q, Q + R are collinear. Then P + (Q + R) = в€’Q.
Also, P + Q = в€’(Q + R), so (P + Q) + R = в€’(Q + R) + R. The second
equation of the following shows that associativity holds in this case.

LEMMA 2.11
Let P1 , P2 be points on an elliptic curve. Then (P1 + P2 ) в€’ P2 = P1 and
в€’(P1 + P2 ) + P2 = в€’P1 .

PROOF The two relations are reп¬‚ections of each other, so it suп¬ѓces to
prove the second one. The line L through P1 and P2 intersects the elliptic
curve in в€’(P1 + P2 ). Regarding L as the line through в€’(P1 + P2 ) and P2
yields в€’(P1 + P2 ) + P2 = в€’P1 , as claimed.

Suppose that i = mj for some i, j. We consider the various cases. By the
above discussion, we may assume that all points in the table of intersections
are п¬Ѓnite, except for в€ћ and possibly X. Note that each i and each mj meets
E in three points (counting multiplicity), one of which is Pij . If the two lines
coincide, then the other two points must coincide in some order.

1. = m1 : Then P, Q, R are collinear, and associativity follows.
1

= m2 : In this case, P, Q, в€ћ are collinear, so P +Q = в€ћ; associativity
2. 1
follows by the direct calculation made above.

В© 2008 by Taylor & Francis Group, LLC
32 CHAPTER 2 THE BASIC THEORY

3. = m1 : Similar to the previous case.
2

4. = m3 : Then P, Q, Q+R are collinear; associativity was proved above.
1

5. = m1 : Similar to the previous case.
3

= m2 : Then P + Q must be В±(Q + R). If P + Q = Q + R, then
6. 2
commutativity plus the above lemma yields

P = (P + Q) в€’ Q = (Q + R) в€’ Q = R.

Therefore,

(P + Q) + R = R + (P + Q) = P + (P + Q) = P + (R + Q) = P + (Q + R).

If P + Q = в€’(Q + R), then

(P + Q) + R = в€’(Q + R) + R = в€’Q

and
P + (Q + R) = P в€’ (P + Q) = в€’Q,
so associativity holds.
7. = m3 : In this case, the line m3 through P and (Q + R) intersects E
2
in в€ћ, so P = в€’(Q + R). Since в€’(Q + R), Q, R are collinear, we have
that P, Q, R are collinear and associativity holds.
8. = m2 : Similar to the previous case.
3

9. = m3 : Since 3 cannot intersect E in 4 points (counting multiplici-
3
ties), it is easy to see that P = R or P = P + Q or Q + R = P + Q or
Q + R = R. The case P = R was treated in the case 2 = m2 . Assume
P = P + Q. Adding в€’P and applying Lemma 2.11 yields в€ћ = Q, in
which case associativity immediately follows. The case Q + R = R is
similar. If Q + R = P + Q, then adding в€’Q and applying Lemma 2.11
yields P = R, which we have already treated.
If i = mj for all i, j, then the hypotheses of the theorem are satisп¬Ѓed, so
the addition is associative, as proved above. This completes the proof of the

REMARK 2.12 Note that for most of the proof, we did not use the
Weierstrass equation for the elliptic curve. In fact, any nonsingular cubic
curve would suп¬ѓce. The identity O for the group law needs to be a point
whose tangent line intersects to order 3. Three points sum to 0 if they lie
on a straight line. Negation of a point P is accomplished by taking the line
through O and P . The third point of intersection is then в€’P . Associativity
of this group law follows just as in the Weierstrass case.

В© 2008 by Taylor & Francis Group, LLC
33
SECTION 2.4 PROOF OF ASSOCIATIVITY

2.4.1 The Theorems of Pappus and Pascal
Theorem 2.6 has two other nice applications outside the realm of elliptic
curves.

THEOREM 2.13 (PascalвЂ™s Theorem)
Let ABCDEF be a hexagon inscribed in a conic section (ellipse, parabola,
or hyperbola), where A, B, C, D, E, F are distinct points in the aп¬ѓne plane.
Let X be the intersection of AB and DE, let Y be the intersection of BC and
EF , and let Z be the intersection of CD and F A. Then X, Y, Z are collinear
(see Figure 2.4).

Figure 2.4
PascalвЂ™s Theorem

REMARK 2.14 (1) A conic is given by an equation q(x, y) = ax2 + bxy +
cy 2 +dx +ey +f = 0 with at least one of a, b, c nonzero. Usually, it is assumed
that b2 в€’4ac = 0; otherwise, the conic degenerates into a product of two linear
factors, and the graph is the union of two lines. The present theorem holds
even in this case, as long as the points A, C, E lie on one of the lines, B, D, F
lie on the other, and none is the intersection of the two lines.
(2) Possibly AB and DE are parallel, for example. Then X is an inп¬Ѓnite
point in P2 .
K
(3) Note that X, Y, Z will always be distinct. This is easily seen as follows:
First observe that X, Y, Z cannot lie on the conic since a line can intersect

В© 2008 by Taylor & Francis Group, LLC
34 CHAPTER 2 THE BASIC THEORY

the conic in at most two points; the points A, B, C, D, E, F are assumed to
be distinct and therefore exhaust all possible intersections. If X = Y , then
AB and BC meet in both B and Y , and therefore the lines are equal. But
this means that A = C, contradiction. Similarly, X = Z and Y = Z.

PROOF Deп¬Ѓne the following lines:

= EF , = AB, = CD, m1 = BC, m2 = DE, m3 = F A.
1 2 3

We have the following table of intersections:

1 2 3
m1 Y B C
m2 E X D
m3 F A Z

 стр. 1(всего 3)СОДЕРЖАНИЕ >>