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

E 2 or k =0.
We are assuming these cases do not happen, and therefore the congruence
just obtained makes sense. Therefore,

Q 1 ∈ E 2 by Theorem 5.8, hence either P 1 ∈

If v p ( m 2 ) < 0, then

2 m 1

m 2

k ≡

1 ≡

(mod p ) ,

as claimed. This shows that the algorithm works.
Anomalous curves are attractive from a co mp utational viewpoint since cal-
culating an integer multiple of a point in E ( F q ) can be done e ciently. In
designing a cryptosystem, one therefore starts with an anomalous curve E
over a small finite field F q and works in E ( F q k ) for a large k . Usually it is
best to work with the subgroup generated by a point whose order is a large
prime number. In particular, will be much larger than p , hence not equal
to p . Therefore, the above attack on anomalous curves does not apply to the
present situation.
Let E be an elliptic curve over F q such that # E ( F q )= q . Then the trace
of the Frobenius φ q is a =1,so

φ q − φ q + q =0 .

This means that q = φ q − φ q . Therefore

q ( x, y )=( x q ,y q )+( x q 2 , −y q 2 ) for all ( x, y ) ∈ E ( F q ) .

The calculation of x q , for example, can be done quickly in a finite field. There-
fore, the expense of multiplying by q is little more than the expense of one
addition of points. The standard method of computing q ( x, y ) (see Section 2.2)
involves more point additions (except when q = 2; but see Exercise 5.8). To
calculate k ( x, y ) for some integer k ,expand k = k 0 + k 1 q + k 2 q 2 + ··· in base
q . Compute k i P for each i , then compute q i k i P . Finally, add these together
to obtain kP .

5.5 Other Attacks

For arbitrary elliptic curves, Baby Step/Giant Step and the Pollard ρ and
λ methods seem to be the best algorithms. There are a few cases where index
calculus techniques can be used in the jacobians of higher genus curves to
solve discrete logarithm problems on certain elliptic curves, but it is not clear
how generally their methods apply. See [45], [46], [79]. See also [113] for a
discussion of some other index calculus ideas and elliptic curves.
An interesting approach due to Silverman [112] is called the xedni calcu-
lus . Suppose we want to find k such that Q = kP on a curve E over F p .