logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

Radical isogeny formulas

Wouter Castryck

( - )

-

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 NN-isogenies emanating from an elliptic curve E over a finite field Fq\mathbb F_q, where N=2,3,N = 2, 3, \ldots is some small fixed integer coprime to qq. The standard approach proceeds by finding a generator of the kernel of the first NN-isogeny, computing its codomain via Vélu's formulas, then finding a generator of the kernel of the second NN-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 NN-isogeny cyclically extending the previous isogeny. These formulas involve the extraction of an NN-th root, therefore we call them "radical isogeny formulas". By varying which NN-th root was chosen (i.e., by scaling the radical with different NN-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.