Accelerating the Delfs-Galbraith Algorithm with Fast Subfield Root Detection

. We give a new algorithm for finding an isogeny from a given supersingular elliptic curve E/ F p 2 to a subfield elliptic curve E (cid:48) / F p , which is the bottleneck step of the Delfs–Galbraith algorithm for the general supersingular isogeny problem. Our core ingredi-ent is a novel method of rapidly determining whether a polynomial f ∈ L [ X ] has any roots in a subfield K ⊂ L , while avoiding expensive root-finding algorithms. In the special case when f = Φ (cid:96),p ( X, j ) ∈ F p 2 [ X ], i.e., when f is the (cid:96) -th modular polynomial evaluated at a supersingular j -invariant, this provides a means of efficiently determining whether there is an (cid:96) -isogeny connecting the corresponding elliptic curve to a subfield curve. Together with the traditional Delfs–Galbraith walk, inspecting many (cid:96) -isogenous neighbours in this way allows us to search through a larger proportion of the supersingular set per unit of time. Though the asymptotic ˜ O ( p 1 / 2 ) 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 (i.e. the foundational problem underlying isogeny-based cryptography), and has immediate implications on the bit-security of schemes like B-SIDH and SQISign for which Delfs–Galbraith is the best known classical attack. Delfs–Galbraith algorithm.