Computing supersingular endomorphism rings using inseparable endomorphisms (Q7008568)

Computing endomorphism rings of supersingular elliptic curves defined over a finite field is a hard problem. Over the years, various approaches have been exploited yet state-of-the-art algorithms remain of exponential complexity in the size of the base field. This is unlike ordinary elliptic curves of which endomorphism rings may be computed in polynomial time.\N\NA key step towards computing endomorphism rings of supersingular elliptic curves is the computation of a nontrivial, inseparable endomorphism. The present paper refines known techniques so as to derive such an endomorphism given just one path from the given elliptic curve \(E\) defined over \(\mathbb F_{p^2}\) to one defined over \(\mathbb F_p\). This improves state-of-the-art by a factor of two.\N\NFurthermore, the proposed algorithms offer more control over the arithmetic properties of the endomorphisms it outputs, allowing the authors to prove that those endomorphisms generate a Bass suborder of the endomorphism ring. In Theorem 5.5, they conclude that, under the GRH, there exists an explicit algorithm which computes the endomorphism ring of a supersingular elliptic curve \(E\) defined over \(\mathbb F_{p^2}\) in expected time \(O(\sqrt{p}(\log p)^2(\log\log p)^3)\).\N\NAlthough no practical computation is presented in this paper, it is notable that the authors have published their SageMath implementation of all algorithms outlined in this paper on GitHub.