Optimal Strategies for Computation of Degree `n Isogenies for SIDH

This article presents methods and algorithms for the computation of isogenies of degree ℓⁿ. Some of these methods are obtained using recurrence equations and generating functions. A standard multiplication based algorithm for computation of isogeny of degree ℓⁿ has time complexity equal to O(n²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: - determination of optimal strategy for computation of degree ℓⁿ isogeny, - determination of cost of optimal strategy of computation of ℓⁿ isogeny using solutions of recurrence equations, - determination of cost of optimal strategy of computation of ℓⁿ isogeny using recurrence equations, 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 (սₘ) and (cₘ) where cₘ 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.