On the feasibility of computing constructive Deuring correspondence
Volume 126 / 2023
Abstract
For a prime $p$, let $E_0$ be a supersingular elliptic curve $E_0$ over $\mathbb{F}_{p^2}$ with $\mathcal{O}_0 = \mathrm{End}(E_0)$. The Deuring correspondence gives a bijection between isogenies $\varphi _I: E_0 \rightarrow E_I$ and left $\mathcal{O}_0$-ideals $I$. We study the feasibility of translating ideals $I$ to isogenies $\varphi _I$ for general $p$. For efficient isogeny computation, we modify the Kohel-Lauter-Petit-Tignol (KLPT) algorithm to find an equivalent ideal $J$ of $I$ so that its reduced norm $\mathrm{Nrd}(J)$ is divisible by primes $\ell $ at which the extension degrees $d = [\mathbb{F}_{p^2}(E_0[\ell ]): \mathbb{F}_{p^2}]$ are bounded by an appropriately chosen $D \gt 0$. In addition, we adopt the random sampling method to find an $\ell $-torsion point of $E_0$ for practical efficiency, and also propose a direct method of finding a generating point of $\mathop{\varphi}_J \cap E_0[\ell ]$. We select a suitable parameter $D$ based on complexity analysis, and show experimental results of our computation.
