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

quickly (using at most a constant times log q point additions on E ). See

Section 11.4.
Technically, we should write τ n ( P, Q )as τ n ( P, Q + nE ( F q )), since an element
of E ( F q ) /nE ( F q ) has the form Q + nE ( F q ). However, we'll simply write
τ n ( P, Q ) and similarly for P, Q n . The fact that τ n is nondegenerate means
that if τ n ( P, Q ) = 1 for all Q then P = ∞ ,andif τ n ( P, Q ) = 1 for all P then
Q ∈ nE ( F q ). Bilinearity means that

τ n ( P 1 + P 1 ,Q )= τ n ( P 1 ,Q ) τ n ( P 2 ,Q )

and

τ n ( P, Q 1 + Q 2 )= τ n ( P, Q 1 ) τ n ( P, Q 2 ) .

PROOF We now prove the theorem. First, we need to show that τ n ( P, Q )
is defined and is independent of the choice of R .Since nR = Q ∈ E ( F q ), we
have

∞ = Q − φ ( Q )= n ( R − φR ) ,

so R − φR ∈ E [ n ] (to lower the number of parentheses, we often write φR
instead of φ ( R )). Since P ∈ E [ n ], too, the Weil pairing e n ( P, R − φR )is
defined. Suppose that nR = Q gives another choice of R .Let T = R − R .
Then nT = Q − Q = ∞ ,so T ∈ E [ n ]. Therefore,

e n ( P, R − φR )= e n ( P, R − φR + T − φT )
= e n ( P, R − φR ) e n ( P, T ) /e n ( P, φT ) .

But P = φP ,since P ∈ E ( F q ), so

e n ( P, φT )= e n ( φP, φT )= φ ( e n ( P, T )) = e n ( P, T ) ,

since e n ( P, T ) ∈ μ n ⊂ F q . Therefore,

e n ( P, R − φR )= e n ( P, R − φR ) ,

so τ n does not depend on the choice of R .
Since Q is actually a representative of a coset in E ( F q ) /nE ( F q ), we need
to show that the value of τ n depends only on the coset, not on the particular
choice of representative. Therefore, suppose Q − Q = nU ∈ nE ( F q ). Let

nR = Q and let R = R + U .Then nR = Q .Wehave

e n ( P, R − φR )= e n ( P, R − φR + U − φU )= e n ( P, R − φR ) ,

since U = φU for U E ( F q ). Therefore, the value does not depend on the

choice of coset representative. This completes the proof that τ n is well defined.
The fact that τ n ( P, Q ) is bilinear in P follows immediately from the cor-
responding fact for e n . For bilinearity in Q , suppose that nR 1 = Q 1 and

∈