An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous best known algorithm has a worst case running time which is exponential in the length of the input. In this paper we show this problem can be solved in subexponential time under reasonable heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of , our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.
Bisson and Sutherland @cite_6 have developed an algorithm to compute the endomorphism ring of an elliptic curve in subexponential time, using relation-finding techniques which largely overlap with ours. Although our main results were obtained independently, we have incorporated their ideas into our algorithm in several places, resulting in a simpler presentation as well as a large speedup compared to the original version of our work. Given two elliptic curves @math and @math over @math admitting a normalized isogeny @math of degree @math , the equation of @math as a rational function contains @math coefficients. @cite_3 have published an algorithm which produces this equation, given @math , @math , and @math . Their algorithm has running time @math , which is quasi-optimal given the size of the output. Using our algorithm, it is possible to compute @math from @math and @math in time @math for large @math . Hence the combination of the two algorithms can produce the equation of @math within a quasi-optimal running time of @math , given only @math and @math (or @math and @math ), without the need to provide @math in the input.
@cite_3 @cite_6
2048276889 2081640523
We survey algorithms for computing isogenies between elliptic curves defined over a field of characteristic either 0 or a large prime. We introduce a new algorithm that computes an isogeny of degree l (l different from the characteristic) in time quasi-linear with respect to l. This is based in particular on fast algorithms for power series expansion of the Weierstrass ℘-function and related functions. Abstract We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field F q . Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of log q , while our bound for the second algorithm depends primarily on log | D E | , where D E is the discriminant of the order isomorphic to End ( E ) . As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed.