-
le 17 janvier 2023 à 10:00
In several applications one is interested in a fast computation of the codomain curve of a long chain of cyclic
-isogenies emanating from an elliptic curve E over a finite field
, where
is some small fixed integer coprime to
. The standard approach proceeds by finding a generator of the kernel of the first
-isogeny, computing its codomain via Vélu's formulas, then finding a generator of the kernel of the second
-isogeny, and so on. Finding these kernel generators is often the main bottleneck.
In this talk I will explain a new approach to this problem, which was studied in joint work with Thomas Decru, Marc Houben and Frederik Vercauteren. We argue that Vélu's formulas can be augmented with explicit formulas for the coordinates of a generator of the kernel of an
-isogeny cyclically extending the previous isogeny. These formulas involve the extraction of an
-th root, therefore we call them "radical isogeny formulas". By varying which
-th root was chosen (i.e., by scaling the radical with different
-th roots of unity) one obtains the kernels of all possible such extensions. Asymptotically, in our main cases of interest this gives a speed-up by a factor 6 or 7 over previous methods.
I will explain the existence of radical isogeny formulas, discuss methods to find them (the formulas become increasingly complicated for larger N), and pose some open questions.