<<

. 3
( 3)



y

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

<<

. 3
( 3)