Elliptic Curves over Finite Fields - Elliptic Curves: Number Theory and Cryptography - page 98

LEMMA 4.5
Let E be defined over F q ,and let ( x, y )

∈ E ( F q ) .

1. φ q ( x, y )

∈ E ( F q )

2. ( x, y )

∈ E ( F q ) ifand onlyif φ q ( x, y )=( x, y ) .

One fact we need is that ( a + b ) q = a q + b q PROOF when q is a power of

the characteristic of the field. We also need that a q = a for all a ∈ F q .See

Appendix C.
Since the proof is the same for the Weierstrass and the generalized Weier-
strass equations, we work with the general form. We have

y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 ,

with a i ∈ F q . Raise the equation to the q th power to obtain

( y q ) 2 + a 1 ( x q y q )+ a 3 ( y q )=( x q ) 3 + a 2 ( x q ) 2 + a 4 ( x q )+ a 6 .

This means that ( x q ,y q ) lies on E , which proves (1).
For (2), again recall that x ∈ F q if and only if φ q ( x )= x (see Appendix C),
and similarly for y . Therefore

( x, y ) ∈ E ( F q ) ⇔ F q

⇔ φ q ( x )= x and φ q ( y )= y
⇔ φ q ( x, y )=( x, y ) .

x, y ∈

LEMMA 4.6
Let E be an elliptic curve defined over F q .Then φ q is an endom orphism of
E of degree q ,and φ q is not separable.

This is the same as Lemma 2.20.
Note that the kernel of the endomorphism φ q is trivial. This is related to
the fact that φ q is not separable. See Proposition 2.21.
The following result is the key to counting points on elliptic curves over
finite fields. Since φ q is an endomorphism of E ,soare φ q = φ q ◦ φ q and also
φ q = φ q ◦ φ q ◦···◦ φ q for every n ≥ 1. Since multiplication by − 1 is also an

endomorphism, the sum φ q − 1 is an endomorphism of E .

PROPOSITION 4.7
Let E be defined over F q and let n ≥ 1 .

1. K er ( φ q − 1) = E ( F q n ) .