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[2], 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

).

Start Free Trial

No credit card required