Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields

Consider the problem of efficiently evaluating isogenies of elliptic curves over a finite field, where the kernel is a cyclic group of odd (prime) order: given, and a point (or several points) P on, we want to compute. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on Vélu’s formulæ give an efficient solution when the kernel generator G is defined over, but for general isogenies is only defined over some extension, even though as a whole (and thus) is defined over the base field ; and the performance of Vélu-style algorithms degrades rapidly as k grows. In this article we revisit isogeny evaluation with a special focus on the case where. We improve Vélu-style evaluation for many cases where using special addition chains, and combine this with the action of Galois to give greater improvements when.