Constructing Isogenies between Elliptic Curves Over Finite Fields

Abstract

Abstract Let E 1 and E 2 be ordinary elliptic curves over a finite field F p such that # E 1 ( F p ) = # E 2 ( F p ). Tate's isogeny theorem states that there is an isogeny from E 1 to E 2 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.