@ARTICLE{Wroński_Michał_Optimal_2020,
author={Wroński, Michał and Chojnacki, Andrzej},
volume={vol. 66},
number={No 3},
journal={International Journal of Electronics and Telecommunications},
pages={465-472},
howpublished={online},
year={2020},
publisher={Polish Academy of Sciences Committee of Electronics and Telecommunications},
abstract={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: determination of optimal strategy for computation of degree ℓn isogeny, determination of cost of optimal strategy of computation of ℓn isogeny using solutions of recurrence equations, determination of cost of optimal strategy of computation of ℓn 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 (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.},
type={Article},
title={Optimal Strategies for Computation of Degree ℓn Isogenies for SIDH},
URL={http://journals.pan.pl/Content/115227/PDF/64_2564_Wronski_L_skl_new1.pdf},
doi={10.24425/ijet.2020.131900},
keywords={SIDH, Optimal strategies, Generating functions},
}