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

6. Repeat with random points T until the least common multiple of the
various d 's obtained is N . This determines k (mod N ).

REMARK 5.2 At first, it might seem that d = 1 will occur very often.
However, the opposite is true because of the structure of E ( F q m ). Recall that

E ( F q m ) Z n 1 ⊕ Z n 2

for some integers n 1 ,n 2 with n 1 |n 2 (possibly, n 1 = 1, in which case the group
is cyclic). Then N n 2 ,since n 2 is the largest possible order of an element

of the group. Let B 1 ,B 2 be points of orders n 1 ,n 2 , respectively, such that
B 1 ,B 2 generate E ( F q m ). Then T = a 1 B 1 + a 2 B 2 .Let e

|

be a prime power

dividing N .Then f a 2 ,then f | n 2 with f ≥ e .If divides M , the order of

T . Therefore, e 1 / ,

the probability is at least this high that the full power e is in d . After a few
choices of T , this should be the case. (Note that our probability estimates
are low, since we never included the possible contribution of the a 1 B 1 term.)
Therefore, a few iterations of the algorithm should yield k .

| d =gcd( M, N ). Since the probability that a 2 is 1 −

Potentially, the integer m could be large, in which case the discrete log
problem in the group F q m , which has order q m

− 1, is just as hard as the
original discrete log problem in the smaller group E ( F q ), which has order
approximately q , by Hasse's theorem. However, for supersingular curves, we
can usually take m = 2, as the next result shows.
Let E be an elliptic curve over F q ,where q is a power of the prime number
p .Then

# E ( F q )= q +1 − a

for some integer a .Thecurve E is called supersingular if a ≡ 0(mod p ).
Corollary 4.32 says that this is equivalent to a =0when q = p ≥ 5.

PROPOSITION 5.3
Let E be an elliptic curve over F q and suppose a = q +1 − # E ( F q )=0 .Let
N be a positive integer. If there existsapoint P ∈ E ( F q ) of order N ,then
E [ N ] ⊆ E ( F q 2 ) .

PROOF The Frobenius endomorphism φ q satisfies φ q −aφ q + q =0. Since
a = 0, this reduces to

φ q = −q.

Let S E [ N ]. Since # E ( F q )= q + 1, and since there exists a point of order

N ,wehave N

∈

| q +1, or − q ≡ 1(mod N ). Therefore

φ q ( S )= −qS =1 · S.