## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required 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 (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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required