Computing supersingular endomorphism rings using inseparable endomorphisms
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.
- A Rigorous Time Bound for Factoring Integers
- Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
- Adventures in Supersingularland
- An algorithm for computing modular forms on \(\Gamma_0(N)\)
- Computing cardinalities of \(\mathbb{Q}\)-curve reductions over finite fields
- Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs
- Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\)
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Constructing supersingular elliptic curves
- Counting points on elliptic curves over finite fields
- Cryptographic hash functions from expander graphs
- Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms
- Deuring for the people: supersingular elliptic curves with prescribed endomorphism ring in general characteristic
- Explicit isomorphisms of quaternion algebras over quadratic global fields
- scientific article; zbMATH DE number 3646999 (Why is no real title available?)
- scientific article; zbMATH DE number 4006420 (Why is no real title available?)
- scientific article; zbMATH DE number 1210367 (Why is no real title available?)
- Identification protocols and signature schemes based on supersingular isogeny problems
- Identifying the matrix ring: algorithms for quaternion algebras and quadratic forms
- Integer multiplication in time \(O(n\log n)\)
- Mathematics of public key cryptography.
- Modern computer algebra
- Modular polynomials via isogeny volcanoes
- On automorphisms of quaternion orders.
- On basic and Bass quaternion orders
- On the class-number of the corpus \(P(\sqrt {-k})\).
- On the quaternion -isogeny path problem
- Orientations and the supersingular endomorphism ring problem
- Probabilistic Algorithms in Finite Fields
- Quaternion algebras
- SQISign: compact post-quantum signatures from quaternions and isogenies
- Supersingular curves you can trust
- Supersingular isogeny graphs and endomorphism rings: reductions and solutions
- The Arithmetic of Elliptic Curves
- The supersingular endomorphism ring and one endomorphism problems are equivalent
- Untersuchungen in der Zahlentheorie der rationalen Quaternionenalgebren.
This page was built for publication: Computing supersingular endomorphism rings using inseparable endomorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7008568)
