## 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

214 CHAPTER 18
Frob
11
ﬁxes one of the three points P, Q, and R, and shifts the other
two. We cannot know which one is ﬁxed, but we can rename them
so that P is ﬁxed and Frob
11
(Q) = R. Then
ψ(Frob
11
) =
11
01
and χ
ψ
(Frob
11
) = 1 + 1 0 (mod 2).
Again, we can tell that there are an even number of points on
E(F
11
). There is O, and there is one point with a second coordinate
of 0, and there must be an even number of points that have a
nonzero second coordinate.
Finally, a cycle type of three means that Frob
q
shifts all three of
the roots of the polynomial, and therefore all three of the points.
We do not know if Frob
7
(P) = Q or Frob
7
(P) = R, but we can again
rename them so that Frob
7
(P) = Q and Frob
7
(Q) = R. Then
ψ(Frob
7
) =
01
11
and χ
ψ
(Frob
7
) = 0 + 1 1 (mod 2).
Now we can tell that there are an odd number of points on E(F
7
).
There is O, and there are no points with a second coordinate of 0,
and, as always, there are an even number of points with a nonzero
second coordinate.
The Proof
In general, how can we verify that χ
ψ
(Frob
q
) 1 + q #E(F
q
)
(mod 2) for any elliptic curve y
2
= x
3
+ Ax + B? First, notice that
1 + q is always even, so we have to check that χ
ψ
(Frob
q
) #E(F
q
)
(mod 2).
Again, we arrange the points on E(F
q
) into three classes:
1. O.
2. Other elements of E(F
q
) that are in E, that is, elements
P = (j, k)inE(F
q
) with k = 0.
3. The remainder of the points in E(F
q
).
ONE- AND TWO-DIMENSIONAL REPRESENTATIONS 215
As before, we know that there are always an even number of points
in the third category, and there is always one point in the ﬁrst
category.
What can we say about the second category? These points
correspond to solutions of x
3
+ Ax + B 0 (mod q), which in turn
correspond to cycles of length 1 in the factorization above. For
example, on the elliptic curve y
2
= x
3
2 when q = 31, there
are three points in the second category, corresponding to the
cycle structure 1 + 1 + 1. When q = 11, there is one point in
the second category corresponding to the cycle structure 1 + 2.
And when q = 7, there are no points in the second category cor-
responding to the cycle structure 3.
To summarize: A cycle structure of types 1 + 1 + 1or1+ 2
corresponds to an even number of points on E(F
q
), and a cycle
structure of type 3 corresponds to an odd number of points.
Back to the representation: A cycle structure of type 1 + 1 + 1
corresponds to the matrix representation
10
01
,
a cycle structure of type 1 + 2 corresponds to the matrix represen-
tation
11
01
,
and a cycle structure of type 3 corresponds to the matrix represen-
tation
01
11
.
Therefore, the cycle structure that predicts even and odd number
of points exactly corresponds to χ
ψ
(Frob
q
).

## 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