On the feasibility of computing constructive Deuring correspondence
Volume 126 / 2023
Abstract
For a prime , 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.
