Torsion Points - Elliptic Curves: Number Theory and Cryptography - page 86

n . We first determine the p -power
torsion on E . By Proposition 2.28, multiplication by p is not separable. By
Proposition 2.21, the kernel E [ p ] of multiplication by p has order strictly less
than the degree of this endomorphism, which is p 2 by Corollary 3.7. Since
every element of E [ p ] has order 1 or p , the order of E [ p ]isapowerof p , hence
must be 1 or p .If E [ p ] is trivial, then E [ p k ] must be trivial for all k .Now
suppose E [ p ] has order p . We claim that E [ p k ] Z p k for all k .Itiseasyto
see that E [ p k ] is cyclic. The hard part is to show that the order is p k ,rather
than something smaller (for example, why can't we have E [ p k ]= E [ p ] Z p
for all k ?). Suppose there exists an element P of order p j . By Theorem 2.22,
multiplication by p is surjective, so there exists a point Q with pQ = P .Since

It remains to consider the case where p |

p j Q = p j− 1 P p j +1 Q = p j P =

= ∞ but ∞ ,

Q has order p j +1 . By induction, there are points of order p k for all k .There-
fore, E [ p k ] is cyclic of order p k .
We can now put everything together. Write n = p r n with r n . ≥ 0and p

Then

E [ n ] E [ n ] ⊕ E [ p r ] .

We have E [ n ] Z n ⊕ Z n ,since p n . We have just showed that E [ p r ]
0or Z p r . Recall that

Z n ⊕ Z p r Z n p r Z n

(see Appendix A). Therefore, we obtain

E [ n ] Z n ⊕ Z n Z n ⊕ Z n .

or

This completes the proof of Theorem 3.2.

3.3 The Weil Pairing

The Weil pairing on the n -torsion on an elliptic curve is a major tool in the
study of elliptic curves. For example, it will be used in Chapter 4 to prove
Hasse's theorem on the number of points on an elliptic curve over a finite
field. It will be used in Chapter 5 to attack the discrete logarithm problem
for elliptic curves. In Chapter 6, it will be used in a cryptographic setting.
Let E be an elliptic curve over a field K and let n be an integer not divisible
by the characteristic of K .Then E [ n ] Z n ⊕ Z n .Let

μ n = {x ∈ K | x n =1 }

be the group of n th roots of unity in K . Since the characteristic of K does
not divide n , the equation x n = 1 has no multiple roots, hence has n roots in