Dividing by y3 /y yields the result.

REMARK 2.27 In terms of di¬erentials (see the previous Remark), we

have (dx/y)—¦± is a translation-invariant di¬erential on E. Therefore it must be

a scalar multiple c± dx/y of dx/y. It follows that every nonzero endomorphism

± satis¬es the hypotheses of Lemma 2.26.

© 2008 by Taylor & Francis Group, LLC

58 CHAPTER 2 THE BASIC THEORY

PROPOSITION 2.28

Let E be an elliptic curve de¬ned over a ¬eld K, and let n be a nonzero

integer. Suppose that multiplication by n on E is given by

n(x, y) = (Rn (x), ySn (x))

for all (x, y) ∈ E(K), where Rn and Sn are rational functions. Then

Rn (x)

= n.

Sn (x)

Therefore, multiplication by n is separable if and only if n is not a multiple

of the characteristic p of the ¬eld.

PROOF Since R’n = Rn and S’n = ’Sn , we have R’n /S’n = ’Rn /Sn .

Therefore, the result for positive n implies the result for negative n.

Note that the ¬rst part of the proposition is trivially true for n = 1. If it

is true for n, then Lemma 2.26 implies that it is true for n + 1, which is the

Rn (x)

sum of n and 1. Therefore, S(x) = n for all n.

We have Rn (x) = 0 if and only if n = Rn (x)/Sn (x) = 0, which is equivalent

to p not dividing n. Since the de¬nition of separability is that Rn = 0, this

proves the second part of the proposition.

Finally, we use Lemma 2.26 to prove a result that will be needed in Sec-

tions 3.2 and 4.2. Let E be an elliptic curve de¬ned over a ¬nite ¬eld Fq .

The Frobenius endomorphism φq is de¬ned by φq (x, y) = (xq , y q ). It is an

endomorphism of E by Lemma 2.20.

PROPOSITION 2.29

Let E be an elliptic curve de¬ned over Fq , where q is a power of the prime p.

Let r and s be integers, not both 0. The endomorphism rφq + s is separable if

and only if p s.

PROOF Write the multiplication by r endomorphism as

r(x, y) = (Rr (x), ySr (x)).

Then

(Rrφq (x), ySrφq (x)) = (φq r)(x, y) = (Rr (x), y q Sr (x))

q q

= Rr (x), y(x3 + Ax + B)(q’1)/2 Sr (x) .

q q

Therefore,

q’1

crφq = Rrφq /Srφq = qRr Rr /Srφq = 0.

© 2008 by Taylor & Francis Group, LLC

59

SECTION 2.10 SINGULAR CURVES

Also, cs = Rs /Ss = s by Proposition 2.28. By Lemma 2.26,

Rrφq +s /Srφq +s = crφq +s = crφq + cs = 0 + s = s.

Therefore, Rrφq +s = 0 if and only if p s.

2.10 Singular Curves

We have been working with y 2 = x3 + Ax + B under the assumption that

x3 + Ax + B has distinct roots. However, it is interesting to see what happens

when there are multiple roots. It will turn out that elliptic curve addition

becomes either addition of elements in K or multiplication of elements in K —

or in a quadratic extension of K. This means that an algorithm for a group

E(K) arising from elliptic curves, such as one to solve a discrete logarithm

problem (see Chapter 5), will probably also apply to these more familiar

situations. See also Chapter 7. Moreover, as we™ll discuss brie¬‚y at the end of

this section, singular curves arise naturally when elliptic curves de¬ned over

the integers are reduced modulo various primes.

We ¬rst consider the case where x3 + Ax + B has a triple root at x = 0, so

the curve has the equation

y 2 = x3 .

The point (0, 0) is the only singular point on the curve (see Figure 2.7). Since

Figure 2.7

y 2 = x3

any line through this point intersects the curve in at most one other point,

© 2008 by Taylor & Francis Group, LLC

60 CHAPTER 2 THE BASIC THEORY

(0, 0) causes problems if we try to include it in our group. So we leave it out.

The remaining points, which we denote Ens (K), form a group, with the group

law de¬ned in the same manner as when the cubic has distinct roots. The

only thing that needs to be checked is that the sum of two points cannot be

(0, 0). But since a line through (0, 0) has at most one other intersection point

with the curve, a line through two nonsingular points cannot pass through

(0, 0) (this will also follow from the proof of the theorem below).

THEOREM 2.30

Let E be the curve y 2 = x3 and let Ens (K) be the nonsingular points on this

curve with coordinates in K, including the point ∞ = (0 : 1 : 0). The map

x

Ens (K) ’ K, (x, y) ’ ∞’0

,

y

is a group isomorphism between Ens (K) and K, regarded as an additive group.

PROOF Let t = x/y. Then x = (y/x)2 = 1/t2 and y = x/t = 1/t3 .

Therefore we can express all of the points in Ens (K) in terms of the parameter

t. Let t = 0 correspond to (x, y) = ∞. It follows that the map of the theorem

is a bijection. (Note that 1/t is the slope of the line through (0, 0) and (x, y),

so this parameterization is obtained similarly to the one obtained for quadratic

curves in Section 2.5.4.)

Suppose (x1 , y1 ) + (x2 , y2 ) = (x3 , y3 ). We must show that t1 + t2 = t3 ,

where ti = xi /yi . If (x1 , y1 ) = (x2 , y2 ), the addition formulas say that

2

y2 ’ y 1

’ x1 ’ x2 .

x3 =

x2 ’ x1

Substituting xi = 1/t2 and yi = 1/t3 yields

i i

2

t’3 ’ t’3

t’2 ’ t’2 ’ t’2 .

2 1

=

3 1 2

t2 ’ t’2

’2

1

A straightforward calculation simpli¬es this to

t’2 = (t1 + t2 )’2 .

3

Similarly,

y2 ’ y 1

’y3 = (x3 ’ x1 ) + y1

x2 ’ x1

may be rewritten in terms of the ti to yield

t’3 = (t1 + t2 )’3 .

3

© 2008 by Taylor & Francis Group, LLC

61

SECTION 2.10 SINGULAR CURVES

Taking the ratio of the expressions for t’2 and t’3 gives

3 3

t3 = t1 + t2 ,

as desired.

If (x1 , y1 ) = (x2 , y2 ), the proof is similar. Finally, the cases where one or

more of the points (xi , yi ) = ∞ are easily checked.

Figure 2.8

y 2 = x3 + x2

We now consider the case where x3 + Ax + B has a double root. By trans-

lating x, we may assume that this root is 0 and the curve E has the equation

y 2 = x2 (x + a)

for some a = 0. The point (0, 0) is the only singularity (see Figure 2.8). Let

Ens (K) be the nonsingular points on E with coordinates in K, including the

point ∞. Let ±2 = a (so ± might lie in an extension of K). The equation for

E may be rewritten as

y2

= a + x.

x

When x is near 0, the right side of this equation is approximately a. Therefore,

E is approximated by (y/x)2 = a, or y/x = ±± near x = 0. This means that

the two “tangents” to E at (0, 0) are

y = ’±x

y = ±x and

(for a di¬erent way to obtain these tangents, see Exercise 2.20).

© 2008 by Taylor & Francis Group, LLC

62 CHAPTER 2 THE BASIC THEORY

THEOREM 2.31

Let E be the curve y 2 = x2 (x + a) with 0 = a ∈ K. Let Ens (K) be the

nonsingular points on E with coordinates in K. Let ±2 = a. Consider the

map

y + ±x

, ∞ ’ 1.

ψ : (x, y) ’

y ’ ±x

1. If ± ∈ K, then ψ gives an isomorphism from Ens (K) to K — , considered

as a multiplicative group.

2. If ± ∈ K, then ψ gives an isomorphism

{u + ±v | u, v ∈ K, u2 ’ av 2 = 1},

Ens (K)

where the right hand side is a group under multiplication.

PROOF Let

y + ±x

.

t=

y ’ ±x

This may be solved for y/x to obtain

y t+1

=± .

t’1

x

Since x + a = (y/x)2 , we obtain

4±2 t 4±3 t(t + 1)

x= and y=

(t ’ 1)2 (t ’ 1)3

(the second is obtained from the ¬rst using y = x(y/x)). Therefore, (x, y)

determines t and t determines (x, y), so the map ψ is injective, and is a

bijection in case (1).

In case (2), rationalize the denominator by multiplying the numerator and

denominator of (y + ±x)/(y ’ ±x) by y + ±x to obtain an expression of the

form u + ±v:

(y + ±x)

= u + ±v.

(y ’ ±x)

We can change the sign of ± throughout this equation and preserve the equal-

ity. Now multiply the resulting expression by the original to obtain

(y + ±x) (y ’ ±x)

u2 ’ av 2 = (u + ±v)(u ’ ±v) = = 1.

(y ’ ±x) (y + ±x)

Conversely, suppose u2 ’ av 2 = 1. Let

2

u+1 u+1

’ a,

x= y= x.

v v

© 2008 by Taylor & Francis Group, LLC

63

SECTION 2.10 SINGULAR CURVES

Then (x, y) is on the curve E and

(y/x) + ± u + 1 + ±v

ψ(x, y) = = = u + ±v

(y/x) ’ ± u + 1 ’ ±v

(the last equality uses the fact that u2 ’ av 2 = 1). Therefore, ψ is surjective,

hence is a bijection in case (2), too.

It remains to show that ψ is a homomorphism. Suppose (x1 , y1 )+(x2 , y2 ) =

(x3 , y3 ). Let

yi + ±xi

ti = .

yi ’ ±xi

We must show that t1 t2 = t3 .

When (x1 , y1 ) = (x2 , y2 ), we have

2

y2 ’ y 1

’ a ’ x1 ’ x2 .

x3 =

x2 ’ x1

4±2 ti 4±3 ti (ti + 1)

Substituting xi = and yi = and simplifying yields

(ti ’ 1)2 (ti ’ 1)3

4t3 4t1 t2

= . (2.11)

(t3 ’ 1)2 (t1 t2 ’ 1)2

Similarly,

y2 ’ y 1

’y3 = (x3 ’ x1 ) + y1

x2 ’ x1

yields

4±3 t3 (t3 + 1) 4±3 t1 t2 (t1 t2 + 1)

= .

(t3 ’ 1)3 (t1 t2 ’ 1)3

The ratio of this equation and (2.11) yields

t3 ’ 1 t 1 t2 ’ 1

= .

t3 + 1 t1 t2 + 1

This simpli¬es to yield

t1 t2 = t3 ,

as desired.

The case where (x1 , y1 ) = (x2 , y2 ) is similar, and the cases where one or

more of the points is ∞ are trivial. This completes the proof.

One situation where the above singular curves arise naturally is when we

are working with curves with integral coe¬cients and reduce modulo various

primes. For example, let E be y 2 = x(x + 35)(x ’ 55). Then we have

E mod 5 : y 2 ≡ x3 ,

E mod 7 : y 2 ≡ x2 (x + 1),

E mod 11 : y 2 ≡ x2 (x + 2).

© 2008 by Taylor & Francis Group, LLC

64 CHAPTER 2 THE BASIC THEORY

The ¬rst case is treated in Theorem 2.30 and is called additive reduction.

The second case is split multiplicative reduction and is covered by The-

orem 2.31(1). In the third case, ± ∈ F11 , so we are in the situation of The-

orem 2.31(2). This is called nonsplit multiplicative reduction. For all

primes p ≥ 13, the cubic polynomial has distinct roots mod p, so E mod p is

nonsingular. This situation is called good reduction.

2.11 Elliptic Curves mod n

In a few situations, we™ll need to work with elliptic curves mod n, where n

is composite. We™ll also need to take elliptic curves over Q and reduce them

mod n, where n is an integer. Both situations are somewhat subtle, as the

following three examples show.

Example 2.7

Let E be given by

y 2 = x3 ’ x + 1 (mod 52 ).

Suppose we want to compute (1, 1) + (21, 4). The slope of the line through

the two points is 3/20. The denominator is not zero mod 25, but it is also

not invertible. Therefore the slope is neither in¬nite nor ¬nite mod 25. If we

compute the sum using the formulas for the group law, the x-coordinate of

the sum is

2

3

’ 1 ’ 21 ≡ ∞ (mod 25).

20

But (1, 1) + (1, 24) = ∞, so we cannot also have (1, 1) + (21, 4) = ∞.

Example 2.8

Let E be given by

y 2 = x3 ’ x + 1 (mod 35).

Suppose we want to compute (1, 1) + (26, 24). The slope is 23/25, which is

in¬nite mod 5 but ¬nite mod 7. Therefore, the formulas for the sum yield a

point that is ∞ mod 5 but is ¬nite mod 7. In a sense, the point is partially

at ∞. We cannot express it in a¬ne coordinates mod 35. One remedy is to

use the Chinese Remainder Theorem to write

E(Z35 ) = E(Z5 ) • E(Z7 )

and then work mod 5 and mod 7 separately. This strategy works well in the

present case, but it doesn™t help in the previous example.

© 2008 by Taylor & Francis Group, LLC

65

SECTION 2.11 ELLIPTIC CURVES MOD N

Example 2.9

Let E be given by

y 2 = x3 + 3x ’ 3

over Q. Suppose we want to compute

571 16379

, ).

(1, 1) + (

361 6859

Since the points are distinct, we compute the slope of the line through them

in the usual way. This allows us to ¬nd the sum. Now consider E mod 7.

The two points are seen to be congruent mod 7, so the line through them

mod 7 is the tangent line. Therefore, the formula we use to add the points

mod 7 is di¬erent from the one used in Q. Suppose we want to show that the

reduction map from E(Q) to E(F7 ) is a homomorphism. At ¬rst, it would

seem that this is obvious, since we just take the formulas for the group law

over Q and reduce them mod 7. But the present example says that sometimes

we are using di¬erent formulas over Q and mod 7. A careful analysis shows

that this does not cause problems, but it should be clear that the reduction

map is more subtle than one might guess.

The remedy for the above problems is to develop a theory of elliptic curves

over rings. We follow [74]. The reader willing to believe Corollaries 2.32, 2.33,

and 2.34 can safely skip the details in this section.

Let R be a ring (always assumed to be commutative with 1). A tuple of

elements (x1 , x2 , . . . ) from R is said to be primitive if there exist elements

r1 , r2 , · · · ∈ R such that

r1 x1 + r2 x2 + · · · = 1.

When R = Z, this means that gcd(x1 , x2 , . . . ) = 1. When R = Zn , primitivity

means that gcd(n, x1 , x2 , . . . ) = 1. When R is a ¬eld, primitivity means that

at least one of the xi is nonzero. In general, primitivity means that the ideal

generated by x1 , x2 , . . . is R. We say that two primitive triples (x, y, z) and

(x , y , z ) are equivalent if there exists a unit u ∈ R— such that

(x , y , z ) = (ux, uy, uz)

(in fact, it follows easily from the existence of r, s, t with rx + sy + tz = 1

that any u satisfying this equation must be a unit). De¬ne 2-dimensional

projective space over R to be

P2 (R) = {(x, y, z) ∈ R3 | (x, y, z) is primitive} mod equivalence.

The equivalence class of (x, y, z) is denoted by (x : y : z).

If R is a ¬eld, P2 (R) is the same as that de¬ned in Section 2.3. If (x :

y : z) ∈ P2 (Q), we can multiply by a suitable rational number to clear

© 2008 by Taylor & Francis Group, LLC

66 CHAPTER 2 THE BASIC THEORY

denominators and remove common factors from the numerators and therefore

obtain a triple of integers with gcd=1. Therefore, P2 (Q) and P2 (Z) will be

regarded as equal. Similarly, if R is a ring with

Z ⊆ R ⊆ Q,

then P2 (R) = P2 (Z).

In order to work with elliptic curves over R, we need to impose two condi-

tions on R.

1. 2 ∈ R—

2. If (aij ) is an m — n matrix such that (a11 , a12 , . . . , amn ) is primitive and

such that all 2—2 subdeterminants vanish (that is, aij ak ’ai akj = 0 for

all i, j, k, ), then some R-linear combination of the rows is a primitive

n-tuple.

The ¬rst condition is needed since we™ll be working with the Weierstrass equa-

tion. In fact, we should add the condition that 3 ∈ R— if we want to change

an arbitrary elliptic curve into Weierstrass form. Note that Z does not satisfy

the ¬rst condition. This can be remedied by working with

x

Z(2) = { | x ∈ Z, k ≥ 0}.

2k

This is a ring. As pointed out above, P2 (Z(2) ) equals P2 (Z), so the introduc-

tion of Z(2) is a minor technicality.

The second condition is perhaps best understood when R is a ¬eld. In this

case, the primitivity of the matrix simply means that at least one entry is

nonzero. The vanishing of the 2 — 2 subdeterminants says that the rows are

proportional to each other. The conclusion is that some linear combination

of the rows (in this case, some row itself) is a nonzero vector.

When R = Z, the primitivity of the matrix means that the gcd of the

elements in the matrix is 1. Since the rows are assumed to be proportional,

there is a vector v and integers a1 , . . . , am such that the ith row is ai v. The

m-tuple (a1 , . . . , am ) must be primitive since the gcd of its entries divides the

gcd of the entries of the matrix. Therefore, there is a linear combination of

the ai ™s that equals 1. This means that some linear combination of the rows

of the matrix is v. The vector v is primitive since the gcd of its entries divides

the gcd of the entries of the matrix. Therefore, we have obtained a primitive

vector as a linear combination of the rows of the matrix. This shows that

Z satis¬es the second condition. The same argument, slightly modi¬ed to

handle powers of 2, shows that Z(2) also satis¬es the second condition.

In general, condition 2 says that projective modules over R of rank 1 are

free (see [74]). In particular, this holds for local rings, for ¬nite rings, and for

Z(2) . These su¬ce for our purposes.

© 2008 by Taylor & Francis Group, LLC

67

SECTION 2.11 ELLIPTIC CURVES MOD N

For the rest of this section, assume R is a ring satisfying 1 and 2. An

elliptic curve E over R is given by a homogeneous equation

y 2 z = x3 + Axz 2 + Bz 3

with A, B ∈ R such that 4A3 + 27B 2 ∈ R— . De¬ne

E(R) = {(x : y : z) ∈ P2 (R) | y 2 z = x3 + Axz 2 + Bz 3 }.

The addition law is de¬ned in essentially the same manner as in Section 2.2,

but the formulas needed are signi¬cantly more complicated. To make a long

story short (maybe not so short), the answer is the following.

GROUP LAW

Let (xi : yi : zi ) ∈ E(R) for i = 1, 2. Consider the following three sets of

equations:

I.

x3 = (x1 y2 ’ x2 y1 )(y1 z2 + y2 z1 ) + (x1 z2 ’ x2 z1 )y1 y2

’A(x1 z2 + x2 z1 )(x1 z2 ’ x2 z1 ) ’ 3B(x1 z2 ’ x2 z1 )z1 z2

y3 = ’3x1 x2 (x1 y2 ’ x2 y1 ) ’ y1 y2 (y1 z2 ’ y2 z1 ) ’ A(x1 y2 ’ x2 y1 )z1 z2

+A(x1 z2 + x2 z1 )(y1 z2 ’ y2 z1 ) + 3B(y1 z2 ’ y2 z1 )z1 z2

z3 = 3x1 x2 (x1 z2 ’ x2 z1 ) ’ (y1 z2 + y2 z1 )(y1 z2 ’ y2 z1 )

+A(x1 z2 ’ x2 z1 )z1 z2

II.

x3 = y1 y2 (x1 y2 + x2 y1 ) ’ Ax1 x2 (y1 z2 + y2 z1 )

’A(x1 y2 + x2 y1 )(x1 z2 + x2 z1 ) ’ 3B(x1 y2 + x2 y1 )z1 z2

’3B(x1 z2 + x2 z1 )(y1 z2 + y2 z1 ) + A2 (y1 z2 + y2 z1 )z1 z2

y3 = y1 y2 + 3Ax2 x2 + 9Bx1 x2 (x1 z2 + x2 z1 )

22

12

’A x1 z2 (x1 z2 + 2x2 z1 ) ’ A2 x2 z1 (2x1 z2 + x2 z1 )

2

’3ABz1 z2 (x1 z2 + x2 z1 ) ’ (A3 + 9B 2 )z1 z2

22

z3 = 3x1 x2 (x1 y2 + x2 y1 ) + y1 y2 (y1 z2 + y2 z1 ) + A(x1 y2 + x2 y1 )z1 z2

+A(x1 z2 + x2 z1 )(y1 z2 + y2 z1 ) + 3B(y1 z2 + y2 z1 )z1 z2

III.

x3 = (x1 y2 + x2 y1 )(x1 y2 ’ x2 y1 ) + Ax1 x2 (x1 z2 ’ x2 z1 )

+3B(x1 z2 + x2 z1 )(x1 z2 ’ x2 z1 ) ’ A2 (x1 z2 ’ x2 z1 )z1 z2

y3 = (x1 y2 ’ x2 y1 )y1 y2 ’ 3Ax1 x2 (y1 z2 ’ y2 z1 )

+A(x1 y2 + x2 y1 )(x1 z2 ’ x2 z1 ) + 3B(x1 y2 ’ x2 y1 )z1 z2

’3B(x1 z2 + x2 z1 )(y1 z2 ’ y2 z1 ) + A2 (y1 z2 ’ y2 z1 )z1 z2

© 2008 by Taylor & Francis Group, LLC

68 CHAPTER 2 THE BASIC THEORY

z3 = ’(x1 y2 + x2 y1 )(y1 z2 ’ y2 z1 ) ’ (x1 z2 ’ x2 z1 )y1 y2

’A(x1 z2 + x2 z1 )(x1 z2 ’ x2 z1 ) ’ 3B(x1 z2 ’ x2 z1 )z1 z2

⎛ ⎞

Then the matrix

x3 y3 z3

⎝ x3 y3 z3 ⎠

x3 y3 z3

is primitive and all 2 — 2 subdeterminants vanish. Take a primitive R-linear

combination (x3 , y3 , z3 ) of the rows. De¬ne

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

Also, de¬ne

’(x1 : y1 : z1 ) = (x1 : ’y1 : z1 ).

Then E(R) is an abelian group under this de¬nition of point addition. The

identity element is (0 : 1 : 0).

For some of the details concerning this de¬nition, see [74]. The equations

are deduced (with a slight correction) from those in [18]. A similar set of

equations is given in [72].

When R is a ¬eld, each of these equations can be shown to give the usual

group law when the output is a point in P2 (R) (that is, not all three coor-

dinates vanish). If two or three of the equations yield points in P2 (R), then

these points are equal (since the 2 — 2 subdeterminants vanish). If R is a ring,

then it is possible that each of the equations yields a nonprimitive output

(for example, perhaps 5 divides the output of I, 7 divides the output of II,

and 11 divides the output of III). If we are working with Z or Z(2) , this is

no problem. Simply divide by the gcd of the entries in an output. But in an

arbitrary ring, gcd™s might not exist, so we must take a linear combination to

obtain a primitive vector, and hence an element in P2 (R).

Example 2.10

Let R = Z25 and let E be given by

y 2 = x3 ’ x + 1 (mod 52 ).

Suppose we want to compute (1, 1) + (21, 4), as in Example 2.7 above. Write

the points in homogeneous coordinates as

(x1 : y1 : z1 ) = (1 : 1 : 1), (x2 : y2 : z2 ) = (21 : 4 : 1).

Formulas I, II, III yield

(x3 , y3 , z3 ) = (5, 23, 0)

(x3 , y3 , z3 ) = (5, 8, 0)

(x3 , y3 , z3 ) = (20, 12, 0),

© 2008 by Taylor & Francis Group, LLC

69

SECTION 2.11 ELLIPTIC CURVES MOD N

respectively. Note that these are all the same point in P2 (Z25 ) since

(5, 23, 0) = 6(5, 8, 0) = 4(20, 12, 0).

If we reduce the point (5 : 8 : 0) mod 5, we obtain (0 : 3 : 0) = (0 : 1 : 0),

which is the point ∞. The fact that the point is at in¬nity mod 5 but not

mod 25 is what caused the di¬culties in our calculations in Example 2.7.

Example 2.11

Let E be an elliptic curve. Suppose we use the formulas to calculate

(0 : 1 : 0) + (0 : 1 : 0).

Formulas I, II, III yield

(0, 0, 0), (0, 1, 0), (0, 0, 0),

respectively. The ¬rst and third outputs do not yield points in projective

space. The second says that

(0 : 1 : 0) + (0 : 1 : 0) = (0 : 1 : 0).

This is of course the rule ∞ + ∞ = ∞ from the usual group law on elliptic

curves.

The present version of the group law allows us to work with elliptic curves

over rings in theoretical settings. We give three examples.

COROLLARY 2.32

Let n1 and n2 be odd integers with gcd(n1 , n2 ) = 1. Let E be an elliptic curve

de¬ned over Zn1 n2 . Then there is a group isomorphism

E(Zn1 ) • E(Zn2 ).

E(Zn1 n2 )

PROOF Suppose that E is given by y 2 z = x3 + Axz 2 + Bz 3 with A, B ∈

Zn1 n2 and 4A3 + 27B 2 ∈ Z—1 n2 . Then we can regard A and B as elements of

n

Zni and we have 4A3 + 27B 2 ∈ Z—i . Therefore, we can regard E as an elliptic

n

curve over Zni , so the statement of the corollary makes sense.

The Chinese remainder theorem says that there is an isomorphism of rings

Zn1 • Zn2

Zn1 n2

given by

x mod n1 n2 ←’ (x mod n1 , x mod n2 ) .

© 2008 by Taylor & Francis Group, LLC

70 CHAPTER 2 THE BASIC THEORY

This yields a bijection between triples in Zn1 n2 and pairs of triples, one in

Zn1 and one in Zn2 . It is not hard to see that primitive triples for Zn1 n2

correspond to pairs of primitive triples in Zn1 and Zn2 . Moreover,

y 2 z ≡ x3 + Axz 2 + Bz 3 (mod n1 n2 )

y 2 z ≡ x3 + Axz 2 + Bz 3 (mod n1 )

⇐’

y 2 z ≡ x3 + Axz 2 + Bz 3 (mod n2 )

Therefore, there is a bijection

ψ : E(Zn1 n2 ) ’’ E(Zn1 ) • E(Zn2 ).

It remains to show that ψ is a homomorphism. Let P1 , P2 ∈ E(Zn1 n2 ) and let

P3 = P1 + P2 . This means that there is a linear combination of the outputs

of formulas I, II, III that is primitive and yields P3 . Reducing all of these

calculations mod ni (for i = 1, 2) yields exactly the same result, namely the

primitive point P3 (mod ni ) is the sum of P1 (mod ni ) and P2 (mod ni ).

This means that ψ(P3 ) = ψ(P1 ) + ψ(P2 ), so ψ is a homomorphism.

COROLLARY 2.33

Let E be an elliptic curve over Q given by

y 2 = x3 + Ax + B

with A, B ∈ Z. Let n be a positive odd integer such that gcd(n, 4A3 +27B 2 ) =

1. Represent the elements of E(Q) as primitive triples (x : y : z) ∈ P2 (Z).

The map

redn : E(Q) ’’ E(Zn )

(x : y : z) ’ (x : y : z) (mod n)

is a group homomorphism.

PROOF If P1 , P2 ∈ E(Q) and P1 + P2 = P3 , then P3 is a primitive point

that can be expressed as a linear combination of the outputs of formulas I, II,

III. Reducing all of the calculations mod n yields the result.

Corollary 2.33 can be generalized as follows.

COROLLARY 2.34

Let R be a ring and let I be an ideal of R. Assume that both R and R/I

satisfy conditions (1) and (2) on page 66. Let E be given by

y 2 z = x3 + Axz 2 + Bz 3

© 2008 by Taylor & Francis Group, LLC

71

EXERCISES

with A, B ∈ R and assume there exists r ∈ R such that

(4A3 + 27B 2 )r ’ 1 ∈ I.

Then the map

redI : E(R) ’’ E(R/I)

(x : y : z) ’ (x : y : z) mod I

is a group homomorphism.

PROOF The proof is the same as for Corollary 2.33, with R in place of

Z and mod I in place of mod n. The condition that (4A3 + 27B 2 )r ’ 1 ∈ I

for some r is the requirement that 4A3 + 27B 2 is a unit in R/I, which was

required in the de¬nition of an elliptic curve over the ring R/I.

Exercises

2.1 (a) Show that the constant term of a monic cubic polynomial is the

negative of the product of the roots.

(b) Use (a) to derive the formula for the sum of two distinct points

P1 , P2 in the case that the x-coordinates x1 and x2 are nonzero, as

in Section 2.2. Note that when one of these coordinates is 0, you

need to divide by zero to obtain the usual formula.

2.2 The point (3, 5) lies on the elliptic curve E : y 2 = x3 ’ 2, de¬ned over

Q. Find a point (not ∞) with rational, nonintegral coordinates in (Q).

2.3 The points P = (2, 9), Q = (3, 10), and R = (’4, ’3) lie on the elliptic

curve E : y 2 = x3 + 73.

(a) Compute P + Q and (P + Q) + R.

(b) Compute Q + R and P + (Q + R). Your answer for P + (Q + R)

should agree with the result of part (a). However, note that one

computation used the doubling formula while the other did not use

it.

2.4 Let E be the elliptic curve y 2 = x3 ’ 34x + 37 de¬ned over Q. Let

P = (1, 2) and Q = (6, 7).

(a) Compute P + Q.

© 2008 by Taylor & Francis Group, LLC

72 CHAPTER 2 THE BASIC THEORY

(b) Note that P ≡ Q (mod 5). Compute 2P on E mod 5. Show that

the answer is the same as (P +Q) mod 5. Observe that since P ≡ Q,

the formula for adding the points mod 5 is not the reduction of the

formula for adding P +Q. However, the answers are the same. This

shows that the fact that reduction mod a prime is a homomorphism

is subtle, and this is the reason for the complicated formulas in

Section 2.11.

2.5 Let (x, y) be a point on the elliptic curve E given by y 2 = x3 + Ax + B.

Show that if y = 0 then 3x2 + A = 0. (Hint: What is the condition for

a polynomial to have x as a multiple root?)

2.6 Show that three points on an elliptic curve add to ∞ if and only if they

are collinear.

2.7 Let C be the curve u2 + v 2 = c2 1 + du2 v 2 , as in Section 2.6.3. Show

that the point (c, 0) has order 4.

2.8 Show that the method at the end of Section 2.2 actually computes kP .

(Hint: Use induction on the length of the binary expansion of k. If

k = k0 + 2k1 + 4k2 + · · · + 2 a , assume the result holds for k = k0 +

2k1 + 4k2 + · · · + 2 ’1 a ’1 .)

2.9 If P = (x, y) = ∞ is on the curve described by (2.1), then ’P is the

other ¬nite point of intersection of the curve and the vertical line through

P . Show that ’P = (x, ’a1 x ’ a3 ’ y). (Hint: This involves solving

a quadratic in y. Note that the sum of the roots of a monic quadratic

polynomial equals the negative of the coe¬cient of the linear term.)

2.10 Let R be the real numbers. Show that the map (x, y, z) ’ (x : y : z)

gives a two-to-one map from the sphere x2 + y 2 + z 2 = 1 in R3 to P2 .

R

Since the sphere is compact, this shows that P2 is compact under the

R

topology inherited from the sphere (a set is open in P2 if and only if

R

its inverse image is open in the sphere).

2.11 (a) Show that two lines a1 x + b1 y + c1 z = 0 and a2 x + b2 y + c2 z = 0

in two-dimensional projective space have a point of intersection.

(b) Show that there is exactly one line through two distinct given points

in P2 .

K

2.12 Suppose that the matrix

⎛ ⎞

a1 b1

M = ⎝ a2 b2 ⎠

a3 b3

has rank 2. Let (a, b, c) be a nonzero vector in the left nullspace of M ,

so (a, b, c)M = 0. Show that the parametric equations

x = a1 u + b1 v, y = a2 u + b2 v, z = a3 u + b3 v,

© 2008 by Taylor & Francis Group, LLC

73

EXERCISES

describe the line ax + by + cz = 0 in P2 . (It is easy to see that the

K

points (x : y : z) lie on the line. The main point is that each point on

the line corresponds to a pair (u, v).)

2.13 (a) Put the Legendre equation y 2 = x(x ’ 1)(x ’ ») into Weierstrass

form and use this to show that the j-invariant is

(»2 ’ » + 1)3

j = 28 .

»2 (» ’ 1)2

(b) Show that if j = 0, 1728 then there are six distinct values of »

giving this j, and that if » is one such value then the full set is

»’1

1 »

1

{», , 1 ’ », }.

, ,

1’» »’1

» »

(c) Show that if j = 1728 then » = ’1, 2, 1/2, and if j = 0 then

»2 ’ » + 1 = 0.

2.14 Consider the equation u2 ’ v 2 = 1, and the point (u0 , v0 ) = (1, 0).

(a) Use the method of Section 2.5.4 to obtain the parameterization

m2 + 1 2m

u= 2 , v= .

m2 ’ 1

m ’1

(b) Show that the projective curve u2 ’ v 2 = w2 has two points at

in¬nity, (1 : 1 : 0) and (1 : ’1 : 0).

(c) The parameterization obtained in (a) can be written in projective

coordinates as (u : v : w) = (m2 + 1 : 2m : m2 ’ 1) (or (m2 + n2 :

2mn : m2 ’ n2 ) in a homogeneous form). Show that the values

m = ±1 correspond to the two points at in¬nity. Explain why this

is to be expected from the graph (using real numbers) of u2 ’v 2 = 1.

(Hint: Where does an asymptote intersect a hyperbola?)

2.15 Suppose (u0 , v0 , w0 ) = (u0 , 0, 0) lies in the intersection

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

(a) Show that the procedure of Section 2.5.4 leads to an equation of

the form “square = degree 2 polynomial in m.”

(b) Let F = au2 + bv 2 = e and G = cu2 + dw2 = f . Show that the

Fu F v F w

at (u0 , 0, 0) has rank 1. Since the

Jacobian matrix

Gu Gv Gw

rank is less than 2, this means that the point is a singular point.

2.16 Show that the cubic equation x3 + y 3 = d can be transformed to the

elliptic curve y1 = x3 ’ 432d2 .

2

1

© 2008 by Taylor & Francis Group, LLC

74 CHAPTER 2 THE BASIC THEORY

2.17 (a) Show that (x, y) ’ (x, ’y) is a group homomorphism from E to

itself, for any elliptic curve in Weierstrass form.

(b) Show that (x, y) ’ (ζx, ’y), where ζ is a nontrivial cube root of

1, is an automorphism of the elliptic curve y 2 = x3 + B.

(c) Show that (x, y) ’ (’x, iy), where i2 = ’1, is an automorphism

of the elliptic curve y 2 = x3 + Ax.

2.18 Let K have characteristic 3 and let E be de¬ned by y 2 = x3 + a2 x2 +

a4 x + a6 . The j-invariant in this case is de¬ned to be

a6

2

j= 2 2

a2 a4 ’ a3 a6 ’ a3

2 4

(this formula is false if the characteristic is not 3).

(a) Show that either a2 = 0 or a4 = 0 (otherwise, the cubic has a triple

root, which is not allowed).

(b) Show that if a2 = 0, then the change of variables x1 = x ’ (a4 /a2 )

yields an equation of the form y1 = x3 + a2 x2 + a6 . This means

2

1 1

that we may always assume that exactly one of a2 and a4 is 0.

(c) Show that if two elliptic curves y 2 = x3 + a2 x2 + a6 and y 2 =

—

x3 + a2 x2 + a6 have the same j-invariant, then there exists µ ∈ K

such that a2 = µ2 a2 and a6 = µ6 a6 .

(d) Show that if y 2 = x3 + a4 x + a6 and y 2 = x3 + a4 x2 + a6 are

two elliptic curves (in characteristic 3), then there is a change of

—

variables y ’ ay, x ’ bx + c, with a, b ∈ K and c ∈ K, that

changes one equation into the other.

(e) Observe that if a2 = 0 then j = 0 and if a4 = 0 then j = ’a3 /a6 .

2

Show that every element of K appears as the j-invariant of a curve

de¬ned over K.

(f) Show that if two curves have the same j-invariant then there is a

change of variables over K that changes one into the other.

2.19 Let ±(x, y) = (p(x)/q(x), y ·s(x)/t(x)) be an endomorphism of the ellip-

tic curve E given by y 2 = x3 + Ax + B, where p, q, s, t are polynomials

such that p and q have no common root and s and t have no common

root.

(a) Using the fact that (x, y) and ±(x, y) lie on E, show that

(x3 + Ax + B) s(x)2 u(x)

=

t(x)2 q(x)3

for some polynomial u(x) such that q and u have no common root.

(Hint: Show that a common root of u and q must also be a root of

p.)

© 2008 by Taylor & Francis Group, LLC

75

EXERCISES

(b) Suppose t(x0 ) = 0. Use the facts that x3 + Ax + B has no multiple

roots and all roots of t2 are multiple roots to show that q(x0 ) = 0.

This shows that if q(x0 ) = 0 then ±(x0 , y0 ) is de¬ned.

2.20 Consider the singular curve y 2 = x3 + ax2 with a = 0. Let y = mx

be a line through (0, 0). Show that the line always intersects the curve

to order at least 2, and show that the order is 3 exactly when m2 = a.

√

This may be interpreted as saying that the lines y = ± ax are the two

tangents to the curve at (0, 0).

2.21 (a) Apply the method of Section 2.5.4 to the circle u2 + v 2 = 1 and

the point (’1, 0) to obtain the parameterization

1 ’ t2 2t

u= , v= .

1 + t2 1 + t2

(b) Suppose x, y, z are integers such that x2 + y 2 = z 2 , gcd(x, y, z) = 1,

and x is even. Use (a) to show that there are integers m, n such

that

x = 2mn, y = m2 ’ n2 , z = m2 + n2 .

Also, show that gcd(x, y, z) = 1 implies that gcd(m, n) = 1 and

that m ≡ n (mod 2).

2.22 Let p(x) and q(x) be polynomials with no common roots. Show that

d p(x)

=0

dx q(x)

(that is, the identically 0 rational function) if and only if both p (x) = 0

and q (x) = 0. (If p or q is nonconstant, then this can happen only in

positive characteristic.)

2.23 Let E be given by y 2 = x3 + Ax + B over a ¬eld K and let d ∈ K — . The

twist of E by d is the elliptic curve E (d) given by y 2 = x3 +Ad2 x+Bd3 .

(a) Show that j(E (d) ) = j(E).

√

(b) Show that E (d) can be transformed into E over K( d).

(c) Show that E (d) can be transformed over K to the form dy1 =

2

x3 + Ax1 + B.

1

2.24 Let ±, β ∈ Z be such that gcd(±, β) = 1. Assume that ± ≡ ’1 (mod 4)

and β ≡ 0 (mod 32). Let E be given by y 2 = x(x ’ ±)(x ’ β).

(a) Let p be prime. Show that the cubic polynomial x(x ’ ±)(x ’ β)

cannot have a triple root mod p.

© 2008 by Taylor & Francis Group, LLC

76 CHAPTER 2 THE BASIC THEORY

(b) Show that the substitution

x = 4x1 , y = 8y1 + 4x1

changes E into E1 , given by

’β ’ ± ’ 1 2 ±β

y1 + x1 y1 = x3 +

2

x1 + x1 .

1

4 16

(c) Show that the reduction mod 2 of the equation for E1 is

y1 + x1 y1 = x3 + ex2

2

1 1

for some e ∈ F2 . This curve is singular at (0, 0).

(d) Let γ be a constant and consider the line y1 = γx1 . Show that if

γ 2 + γ = e, then the line intersects the curve in part (c) to order

3, and if γ 2 + γ = e then this line intersects the curve to order 2.

(e) Show that there are two distinct values of γ ∈ F2 such that γ 2 +γ =

e. This implies that there are two distinct tangent lines to the curve

E1 mod 2 at (0,0), as in Exercise 2.20.

We take the property of part (e) to be the de¬nition of multiplicative

reduction in characteristic 2. Therefore, parts (a) and (e) show that

the curve E1 has good or multiplicative reduction at all primes. A

semistable elliptic curve over Q is one that has good or multiplicative

reduction at all primes, possibly after a change of variables (over Q)

such as the one in part (b). Therefore, E is semistable. See Section 15.1

for a situation where this fact is used.

© 2008 by Taylor & Francis Group, LLC