Constructing isogenies between elliptic curves over finite fields

Abstract: Let E₁ and E₂ be ordinary elliptic curves over a finite field E_p such that #E₁(F_p) = #E₂(F_p). Tate's isogeny theorem states that there is an isogeny from E₁ to E₂ which is defined over F_p. The goal of this paper is to describe a probabilistic algorithm for constructing such an isogeny. The algorithm proposed in this paper has exponential complexity in the worst case. Nevertheless, it is efficient in certain situations (that is, when the class number of the endomorphism ring is small). The significance of these results to elliptic curve cryptography is discussed.