Paper 2021/1488

Accelerating the Delfs-Galbraith algorithm with fast subfield root detection

Abstract

We give a new algorithm for finding an isogeny from a given supersingular elliptic curve $E/{\mathbb{F}}_{p^2}$ to a subfield elliptic curve $E^{\prime }/{\mathbb{F}}_p$, which is the bottleneck step of the Delfs-Galbraith algorithm for the general supersingular isogeny problem. Our core ingredient is a novel method of rapidly determining whether a polynomial $f\in L[X]$ has any roots in a subfield $K\subset L$, while crucially avoiding expensive root-finding algorithms. In the special case when $f={\mathrm{\Phi }}_{\ell ,p}(X,j)\in {\mathbb{F}}_{p^2}[X]$, i.e. when $f$ is the $\ell$-th modular polynomial evaluated at a supersingular $$-invariant, this provides a means of efficiently determining whether there is an $$-isogeny connecting the corresponding elliptic curve to a subfield curve. Together with the traditional Delfs-Galbraith walk, inspecting many $$-isogenous neighbours in this way allows us to search through a larger proportion of the supersingular set per unit of time. Though the asymptotic $$ complexity of our improved algorithm remains unchanged from that of the original Delfs-Galbraith algorithm, our theoretical analysis and practical implementation both show a significant reduction in the runtime of the subfield search. This sheds new light on the concrete hardness of the general supersingular isogeny problem, the foundational problem underlying isogeny-based cryptography.

Note: The latest version includes changes to experimental results in light of a change to the accompanying code, which resulted in a better choice of "optimal sets".