The Discrete Logarithm Problem - Elliptic Curves: Number Theory and Cryptography - page 157

E [ ] ⊆ E ( F q ) ,and q ( q − 1) .Then

E [ ] ⊆ E ( F q m ) ifand onlyif q m ≡ 1(mod ) .

If E [ ] ⊆ E ( F q m ), then μ ⊆ F q m by Corollary 3.11, hence q m PROOF ≡ 1

(mod ).
Conversely, suppose q m ≡ 1(mod ). Let P ∈ E ( F q )haveorder and let

Q E ( F q ). We claim that P and Q are independent points of

order .Ifnot,then uP = vQ for some integers u, v

∈ E [ ]with Q ∈

≡ 0(mod ). Multiplying

by v − 1 (mod ), we find that Q = v − 1 uP ∈ E ( F q ), which is a contradiction.

Therefore is a basis for E [ ].

Let φ q be the Frobenius map. The action of φ q on the basis {P, Q} of
E [ ]givesusamatrix( φ q ) , as in Section 3.1. Since P ∈ E ( F q ), we have
φ q ( P )= P .Let φ q ( Q )= bP + dQ .Then
( φ q ) = 1 b

{ P, Q }

.

0 d

From Theorem 4.10, we know that

Trace(( φ q ) ) ≡ a = q +1 − # E ( F q )(mod ) .

Since # E ( F q ) ≡ 0(mod ) by assumption, we have

1+ d ≡ q +1 (mod ) ,

so d ≡ q (mod ). An easy induction shows that

1 b
0 q

m

= 1 b q m − 1

.

q − 1

q m 0

Since q ≡ 1(mod ), by assumption, we have

φ q =1on E [ ] ⇐⇒ ( φ q ) m (mod ) ⇐⇒ q m ≡ I ≡ 1(mod ) .

Since E [ ] ⊆ E ( F q m ) if and only if φ q =1on E [ ], by Lemma 4.5, this proves
the proposition.

If we have E [ n ] ⊆ E ( F q m ), then we can use the MOV attack or we can
use the Tate-Lichtenbaum pairing to reduce discrete log problems in E ( F q m )
to discrete log problems in F q m . The Tate-Lichtenbaum pairing is generally
faster (see [44]). In both cases, we pick arbitrary points R and compute their
pairings with P and kP . With high probability (as in Section 5.3.1), we obtain
k after using only a few values of R .