Solving the Constructive Deuring Correspondence via the Kohel-Lauter-Petit-Tignol Algorithm

Abstract

For an odd prime p, let E₀ be a supersingular elliptic curve over GF(p²) with O₀ = End(E₀). The Deuring correspondence gives a one-to-one correspondence between isogenies φ_I: E₀ → E_I and left O₀-ideals I. The constructive Deuring correspondence is equivalent to the problem that computes the j-invariant of the curve E_I corresponding to given I. In this paper, we compute the j-invariant of E_I via the Kohel-Lauter-Petit-Tignol (KLPT) algorithm that seeks an ideal J of smooth reduced norm Nrd(J) such that E_J ≃ E_I. The target j-invariant can be obtained by computing φ_J: E₀ → E_J. For every prime factor ℓ of Nrd(J), we use symbolic formulas related with isogenies to compute a basis of the ℓ-torsion group E₀[ℓ], a bottleneck part in computing φ_J. We demonstrate the efficacy of our method by showing our implementation results for numerical examples in primes p of up to 25 bits.