212 CHAPTER 18

How can we see that there are always an even number of points

in #E(F

q

)? The argument is very similar to the one that we used

for the elliptic curve y

2

= x

3

− x. In this case, we can divide up the

points on E into three types:

1. O.

2. Elements of E(F

q

) of the form (x,0).

3. The rest of E(F

q

).

We know that there is exactly one point in the ﬁrst set. The

element (1, 0) is always in the second set, so the question is whether

there is one element in the second set or three (depending on

whether or not −3 is a perfect square in F

q

). Either way, there

are an even number of elements between the ﬁrst two sets, and

the third set always has an even number of elements, for exactly

the same reason as before: If (j, k) is a point on the elliptic curve,

so is (j, −k).

Yet Another Example

We now consider a more complicated example. Let E be the elliptic

curve y

2

= x

3

− 2. In this case, the three solutions to x

3

− 2 = 0

are

3

√

2, ω

3

√

2, and ω

2

3

√

2. The elements of E[2] (other than O) are

P = (

3

√

2, 0), Q = (ω

3

√

2, 0), and R = (ω

2

3

√

2, 0). Again, you can check

that P + Q = R.

Pick a prime q. We would like to know how Frob

q

shifts these

three points around, which is the same as knowing how Frob

q

shifts around the three roots of x

3

− 2. For any particular q,wecan

work this out, but we appeal instead to Theorem 16.1. That is the

theorem that tells us that we can ﬁnd out the cycle type of Frob

q

as a permutation of the roots of x

3

− 2 by factoring x

3

− 2 modulo q.

There are three possibilities:

(1) x

3

− 2 factors into three linear factors modulo q. For example,

if q = 31, you can check that

x

3

− 2 ≡ (x + 11)(x + 24)(x + 27) (mod 31)

ONE- AND TWO-DIMENSIONAL REPRESENTATIONS 213

by multiplying out (x +11)(x +24)(x +27) =x

3

+62x

2

+1209x +7128

and reducing that polynomial modulo 31. In this case, the cycle

type of Frob

q

is 1 + 1 + 1.

We can also tell from this factorization that (−11)

3

≡ 2 (mod 31)

and (−24)

3

≡ 2 (mod 31) and (−27)

3

≡ 2 (mod 31). In other words,

we know that there are three points on E(F

31

) whose second

coordinate is 0: (−11, 0), (−24, 0), and (−27, 0).

(2) x

3

− 2 factors into a linear and a quadratic factor modulo q.

For example, if q = 11, then

x

3

− 2 ≡ (x + 4)(x

2

+ 7x + 5) (mod 11),

where x

2

+ 7x + 5 does not factor any more modulo 11. You can

check the factorization by computing (x + 4)(x

2

+ 7x + 5) = x

3

+

11x

2

+ 33x + 20 and reducing modulo 11. In this case, the cycle type

of Frob

q

is 1 + 2.

We can also tell from this factorization that (−4)

3

≡ 2 (mod 11),

and that there is one point on E(F

11

) that has a second coordinate

of 0: (−4, 0).

(3) x

3

− 2 does not factor at all modulo q. For example, if q = 7,

x

3

− 2 does not factor modulo 7. In this case, the cycle type of

Frob

q

is 3.

This factorization tells us that in E(F

7

), there are no points

with a second coordinate of 0.

A cycle type of 1 + 1 + 1 means that Frob

q

does not shift around

the roots of the polynomial. So we know that Frob

31

ﬁxes the roots

of x

3

− 2, which in turn means that Frob

31

(P) = P, Frob

31

(Q) = Q,

and Frob

31

(R) = R. Therefore,

ψ(Frob

31

) =

10

01

and χ

ψ

(Frob

31

) = 1 + 1 ≡ 0 (mod 2).

We can also tell that there are an even number of points in E(F

31

).

There is O, and there are three points with a second coordinate of

0, and there must be an even number of points that have a nonzero

second coordinate.

A cycle type of 1 + 2 means that Frob

q

ﬁxes one of the three roots

of the polynomial, and shifts around the other two. So we know that

Start Free Trial

No credit card required