Paper 2026/1516

Complex-Multiplication Terminals for Supersingular Isogeny Path-Finding

Abstract

We propose a complementary stopping strategy based on complex multiplication (CM) for the subfield-search stage of supersingular isogeny path-finding, a bottleneck in the Delfs-Galbraith/SuperSolver algorithm. The original search performs a non-backtracking walk in the supersingular \(2\)-isogeny graph until it reaches the subfield terminal set \(S_p\). Our idea is to enlarge the set of recognizable terminals, by adding a precomputed set of CM supersingular vertices. For a discriminant bound \(M\), we construct \(S_{\mathrm{CM}}(M)\) from roots of Hilbert class polynomials \(H_D(X)\) over \(\mathbb F_{p^2}\), where \(D\) ranges over inert negative fundamental discriminants with \(|D|<M\). The walk then stops upon reaching \(S_p\cup S_{\mathrm{CM}}(M)\). The only additional per-visit cost is an expected \(O(1)\) hash-table membership query in the precomputed CM terminal table. We estimate the size and preprocessing cost of \(S_{\mathrm{CM}}(M)\), obtaining the heuristic growth \(|S_{\mathrm{CM}}(M)|=\Theta(M^{3/2})\), and show that the overlap \(S_{\mathrm{CM}}(M)\cap S_p\) is lower order. We also give terminal-connection procedures showing how searches that stop at CM vertices can be converted into full isogeny paths under the standard quaternionic and KLPT heuristics. The method does not change the asymptotic exponent of the underlying Delfs-Galbraith search; instead, it provides a complementary technique for existing subfield-search methods by adding efficiently recognizable CM terminals. Experiments on small parameters show that enlarging the terminal union reduces both visited vertices and field multiplications, while lookup benchmarks at SQIsign parameters confirm that the additional table membership test has stable and moderate per-visit overhead.