This article presents methods and algorithms for the computation of isogenies of degree ℓn. Some of these methods are obtained using recurrence equations and generating functions. A standard multiplication based algorithm for computation of isogeny of degree ℓn has time complexity equal to O(n2 M (n log n)), where M(N) denotes the cost of integers of size N multiplication. The memory complexity of this algorithm is equal to O (n log (n log (n))). In this article are presented algorithms for:
where optimality in this context means that, for the given parameters, no other strategy exists that requires fewer operations for computation of isogeny.
Also this article presents a method using generating functions for obtaining the solutions of sequences (um) and (cm) where cm denotes the cost of computations of isogeny of degree ℓum for given costs p; q of ℓ-isogeny computation and ℓ-isogeny evaluation. These solutions are also used in the construction of the algorithms presented in this article.