Page 295 -

272 13. Elliptic Curves over Finite Fields

¯
¯
are isomorphic. Since Gal(k/k) acts semisimply on V (E) by (8.2), the Gal(k/k)-
q
module structure over Q is determined by the trace of σ where σ(a) = a or π,
that is, by the cardinality of E(k). This gives the equivalence of (1), (2), and (3).
Finally, (3) and (4) are equivalent by (2.2) for N 1 determines all the N m . This proves
the theorem.
√
Consider integers a with |a|≤ 2 q. We ask whether there is an elliptic curve
E/F q with #E(F q ) = q + 1 − a or equivalently with Tr(π E ) = a. The problem was
solved more generally for abelian varieties by Honda [1968], see also Tate [1968].
We only state the result.
√ 2
(8.5) Theorem. Let a be an integer with |a|≤ 2 q. If a ≡ 0 (mod q),thena ≡ 0
(mod q). Then there exists an elliptic curve E over F q with #E(F q ) = 1 + q − aor
equivalently Tr(π E ) = a.
(8.6) Example. For p = 2and N = #E(F 2 ) we have for s = 1, 2, 3
a
q = 2, q + 1 = 3 possible N = 1, 2, 3, 4, 5.
q = 4, q + 1 = 5 possible N = 1, 2, 3, 4, 5, 6, 7, 8, 9.
q = 8, q + 1 = 9 possible N = 4, 5, 6, 8, 9, 10, 12, 13, 14.
Observe that 9 − 2 = 7 and 9 + 2 = 11 are missing values for q = 8.

§9. Division Polynomial

The division polynomial is associated with multiplication by N on an elliptic curve
E over a field k. It is polynomial ψ N (x) in the ring generated by the coefficients of
2
the equation for E and of degree (N − 1)/2 when N is odd. We begin our sketch of
the theory with the statement of a general result for an elliptic curve over any field
giving a polynomial in two variables ψ N (x, y), called the Nth division polynomial.

(9.1) Proposition. Let E be an elliptic curve over a field k with coefficients a i , and
let N > 0 be an odd number. There exist polynomials ψ N (x, y), θ N (x, y), ω N (x, y) ∈
Z[x, y, a i ] such that multiplication by N on (x, y) ∈ E(k) −{0} is given by

θ N (x, y) ω N (x, y)
[N](x, y) = , .
ψ N (x, y) 2 ψ N (x, y) 3
The polynomials θ N and ω N are polynomials in ψ N .

A general reference for this subject is Silverman [1994] GTM 151, for this asser-
tion see pp. 105.
Over a field of characteristic = 2, 3 the situation simplifies to a single series of
polynomials ψ N (x) describing [N](x, y), for the dependence of ψ N (x, y) simplifies
significantly. Here a reference is also Blake, Seroussi, and Smart [1999] LMS 265,
pp. 39–42.