Cryptography Reference
In-Depth Information
An algorithm to solve the isogeny problem, requiring exponential time and space in
terms of the input size, was given by Galbraith [ 200 ]. For the case of ordinary elliptic
curves, an improved algorithm with low-storage requirements was given by Galbraith,
Hess and Smart [ 204 ]. We briefly sketch both algorithms in this section.
We now make some preliminary remarks in the ordinary case. Let c 1 be the conductor
of End( E ) and c 2 the conductor of End( E ). If there is a large prime that divides c 1 but
not c 2 (or vice versa), then any isogeny between E and E will have degree divisible by
and hence the isogeny will be slow to compute. Since the conductor is a square factor of
t 2
4 q it can be, in theory, as big as q 1 / 2 . It follows that one does not expect an efficient
algorithm for this problem in general. However, as mentioned in Remark 25.4.11 , one can
in practice ignore this bad case and assume the primes dividing the conductor are moderate.
For the rest of this section, in the ordinary case, we assume that End( E )
End( E )
=
= O
.
(If this is not the case then take vertical isogenies from E to reduce to it.) Usually
is the
maximal order. This is desirable, because the class number of the maximal order is typically
smaller (and never larger) than the class number of the sub-orders, and so the algorithm to
find the isogeny works more quickly in this case. However, for the sake of generality we
do not insist that
O
is the maximal order. The general case could appear if there is a very
large prime dividing the conductor of
O
O
.
25.5.1 The Galbraith algorithm
The algorithm of Galbraith [ 200 ] finds a path between two vertices in the isogeny graph
X E, k ,S using a breadth-first search (see Section 22.2 of [ 136 ]). This algorithm can be used in
both the ordinary and supersingular cases. More precisely, one starts with sets X 0 ={
j ( E )
}
j ( E )
and Y 0 ={
(we are assuming the vertices of the isogeny graph are labelled by j -
invariants) and, at step i , computes X i =
}
δ v ( Y i 1 ) where
δ v ( X ) is the set of vertices in the graph that are connected to a vertex in X by an edge.
Computing δ v ( X ) involves finding the roots in
X i 1
δ v ( X i 1 ) and Y i =
Y i 1
k
of ( j,y ) for every j
X and every
S . In the supersingular case, the set S of possible isogeny degrees usually consists of
asingleprime . In the ordinary case, S could have as many as log( q ) elements, and one
might not compute the whole of δ v ( X ) but just the boundary in a subgraph corresponding to
a (random) subset of S . In either case, the cost of computing δ v ( X ) is clearly proportional
to # X . 14
The algorithm stops when X i
Y i = ∅
, in which case it is easy to compute the
isogeny from E to E .
Exercise 25.5.1 Write pseudocode for the above algorithm.
Under the (probably unreasonable) assumption that new values in δ v ( X i ) behave like
uniformly chosen elements in the isogeny graph, one expects from the birthday paradox
that the two sets have non-empty intersection when # X i +
# Y i π # X E, k ,S . Since the
14
When all S are used at every step, to compute δ v ( X i ) it suffices to consider only vertices j δ v ( X i 1 ).
Search WWH ::




Custom Search