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

By Lemma 4.5, S ∈ E ( F q 2 ), as claimed.

Therefore, discrete log problems over F q for supersingular curves with a =0
can be reduced to discrete log calculations in F q 2 . These are much easier.
When E is supersingular but a = 0, the above ideas work, but possibly

m = 3, 4, or 6 (see [80] and Exercise 5.12). This is still small enough to speed
up discrete log computations.

5.3.2 The Frey-Ruck Attack

Frey and Ruck showed that in some situations, the Tate-Lichtenbaum pair-
ing τ n can be used to solve discrete logarithm problems (see [41] and also
[40]). First, we need the following.

LEMMA 5.4
Let be a primewith

# E ( F q ) ,and 2 # E ( F q ) .Let P be a

generator of E ( F q )[ ] .Then τ ( P, P ) isaprimitive throotofunity.

| q − 1 , |

PROOF If τ ( P, P )=1,then τ ( uP, P )=1 u =1forall u ∈ Z .Since
τ is nondegenerate, P ∈ E ( F q ). Write P = P 1 .Then 2 P 1 = P = ∞ .
Since 2 # E ( F q ), there are no points of order 2 . Therefore P 1 must have

order 1 or .Inparticular, P = P 1 =

∞ , which is a contradiction. Therefore

τ ( P, P ) = 1, so it must be a primitive th root of unity.

Let E ( F q )and P be as in the lemma, and suppose Q = kP . Compute
τ ( P, Q )= τ ( P, P ) k .
Since τ ( P, P ) is a primitive th root of unity, this determines k (mod ). We
have therefore reduced the discrete log problem to one in the multiplicative
group of the finite field F q . Such discrete log problems are usually easier to
solve.
Therefore, to choose a situation where the discrete log problem is hard, we
should choose a situation where there is a point of order ,where is a large
prime, and such that q− 1. In fact, we should arrange that q m

≡ 1(mod )

for small values of m .
Suppose E ( F q ) has a point of order n , but n q − 1. We can extend our
field to F q m so that n|q m − 1. Then the Tate-Lichtenbaum pairing can be

used. However, the following proposition from [9] shows, at least in the case
n is prime, that the Weil pairing also can be used.

PROPOSITION 5.5
Let E be an elliptic curve over F q .Let be a primesuchthat | # E ( F q ) ,