Optimal strategies for computation of degree $\ell^n$ isogenies for SIDH

Abstract

This article presents methods and algorithms for the computation of isogenies of degree $\ell^n$. Some of these methods are obtained using recurrence equations and generating functions. A standard multiplication based algorithm for computation of isogeny of degree $\ell^n$ has time complexity equal to $O(n^2 M \left(n \log{n} \right) )$, where $M(N)$ denotes the cost of integers of size $N$ multiplication. The memory complexity of this algorithm is equal to $O\left( n \log{\left( n \log{(n)} \right)} \right)$. In this article are presented algorithms for:\begin{itemize}\item determination of optimal strategy for computation of degree $\ell^n$ isogeny,\item determination of cost of optimal strategy of computation of $\ell^n$ isogeny using solutions of recurrence equations,\item determination of cost of optimal strategy of computation of $\ell^n$ isogeny using recurrence equations,\end{itemize}where optimality in this context means that, for the given parameters, no other strategy exists that requires fewer operations for faster computation of isogeny. Also this article presents a method using generating functions for obtaining the solutions of sequences $\left( u_m \right)$ and $\left( c_m \right)$ where $c_m$ denotes the cost of computations of isogeny of degree $\ell^{u_m}$ computations for given costs $p,q$ of $\ell$-isogeny computation and $\ell$-isogeny evaluation. These solutions are also used in the construction of the algorithms presented in this article.