Cryptography Reference
In-Depth Information
is very large, one can more efficiently resolve the issue of whether or not
divides the
conductor by finding elements in the ideal class group that are trivial for the maximal
order but non-trivial for an order whose conductor is divisible by
; one can then “test”
such a relation using isogenies. Using these ideas Kohel proves in Theorem 24 of [
315
]
that, assuming a certain generalisation of the Riemann hypothesis, his algorithm requires
O
(
q
1
/
3
+
) bit operations. Kohel also considers the case of supersingular curves.
Bisson and Sutherland [
54
] consider a randomised version of Kohel's method using
ideas from index calculus algorithms in ideal class
g
roups. Their algorithm has heuristic
subexponential expected complexity of
O
(
L
q
(1
/
2
,
√
3
/
2)) bit operations. We do not present
the details.
Remark 25.4.11
An important remark is that neither of the two efficient ways to generate
elliptic curves over finite fields is likely to lead to elliptic curves
E
such that the conductor
of End(
E
) is divisible by a large prime.
When generating elliptic curves by choosing a random curve over a large prime field and
counting points, then
t
2
4
q
behaves like a random integer and so is extremely unlikely
to be divisible by the square of a very large prime
−
When using the CM method then it is automatic that the curves have
q
+
1
−
t
points
where
t
2
4
q
has a very large square factor. It is easy to arrange that the square factor
is divisible by a large prime. However, the elliptic curve itself output by the CM method
has End(
E
) being the maximal order. To get End(
E
) to be a non-maximal order, one
can either use class polynomials corresponding to non-maximal orders or use descending
isogenies. Either way, it is infeasible to compute a curve
E
such that a very large prime
divides the conductor of End(
E
). Furthermore, Kohel's algorithm is not needed in this
case since by construction one already knows End(
E
).
−
Hence, in practice, the potential problems with large primes dividing the conductor of
End(
E
) do not arise. It is therefore safe to assume that determining End(
E
)iseasy.
25.5 Constructing isogenies between elliptic curves
The
isogeny problem for elliptic curves
is: given two elliptic curves
E
and
E
over
F
q
with
the same number of points to compute an isogeny between them. Solving this problem is
usually considered in two stages:
1. Performing a pre-computation, that computes a chain of prime-degree isogenies from
E
to
E
. The chain is usually computed as a sequence of explicit isogenies, though one
could store just the “Elkies inf
o
rmation” for each isogeny in the chain.
2. Given a specific point
P
∈
E
(
F
q
) to compute the image of
P
under the isogeny.
The precomputation is typically slow, while it is desirable that the computation of the
isogeny be fast (since it might be performed for a large number of points).
