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. A 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. Furthermore, 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)\). Although 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)