Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings

• URL: http://arxiv.org/abs/2402.05059v1
• Date: Wed, 7 Feb 2024 18:10:54 GMT
• Title: Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings
• Authors: Kirsten Eisentraeger, Gabrielle Scullard,
• Abstract summary: We give a deterministic time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a deterministic polynomial time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p, provided that we are given two noncommuting endomorphisms and the factorization of the discriminant of the ring $\mathcal{O}_0$ they generate. At each prime $q$ for which $\mathcal{O}_0$ is not maximal, we compute the endomorphism ring locally by computing a q-maximal order containing it and, when $q \neq p$, recovering a path to $\text{End}(E) \otimes \mathbb{Z}_q$ in the Bruhat-Tits tree. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring. Our algorithm improves on a previous algorithm which requires a restricted input and runs in subexponential time under certain heuristics. Page and Wesolowski give a probabilistic polynomial time algorithm to compute the endomorphism ring on input of a single non-scalar endomorphism. Beyond using techniques of higher-dimensional isogenies to divide endomorphisms by a scalar, our methods are completely different.

Related papers

• Computing Isomorphisms between Products of Supersingular Elliptic Curves [0.9467360130705919]
  Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. We present methods for explicitly computing these isomorphisms in time, given the rings of the curves involved.
  arXiv  Detail & Related papers  (2025-03-27T14:26:31Z)
• The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
  We prove that the endomorphism ring of E can be computed in classical time. We also prove that the action of smooth ideals on elliptic curves can be computed in time.
  arXiv  Detail & Related papers  (2023-09-21T09:22:43Z)
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent [5.01069065110753]
  The endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves. We introduce a flexible framework for the study of isogeny graphs with additional information.
  arXiv  Detail & Related papers  (2023-09-19T08:47:12Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields [0.0]
  The Jacobian of an imaginary hyperelliptic curve defined over $mathbb F_q$ acts on a subset of isomorphism classes of Drinfeld modules. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. We prove that the problem of inverting the group action reduces the problem of finding isogenies of fixed $tau$-degree between Drinfeld $mathbb F_q[X]$-modules.
  arXiv  Detail & Related papers  (2022-03-14T10:11:35Z)
• q-Paths: Generalizing the Geometric Annealing Path using Power Means [51.73925445218366]
  We introduce $q$-paths, a family of paths which includes the geometric and arithmetic mixtures as special cases. We show that small deviations away from the geometric path yield empirical gains for Bayesian inference.
  arXiv  Detail & Related papers  (2021-07-01T21:09:06Z)
• Trotter product formulae for $*$-automorphisms of quantum lattice systems [0.0]
  We show that $tau_t$ can be efficiently approximated by a product of $n$ automorphisms. Our bounds hold in norm, pointwise for algebra elements that are sufficiently well approximated by finite volume observables.
  arXiv  Detail & Related papers  (2021-05-29T01:09:21Z)
• The Geometry of Time in Topological Quantum Gravity of the Ricci Flow [62.997667081978825]
  We continue the study of nonrelativistic quantum gravity associated with a family of Ricci flow equations. This topological gravity is of the cohomological type, and it exhibits an $cal N=2$ extended BRST symmetry. We demonstrate a standard one-step BRST gauge-fixing of a theory whose fields are $g_ij$, $ni$ and $n$, and whose gauge symmetries consist of (i) the topological deformations of $g_ij$, and (ii) the ultralocal nonrelativistic limit of space
  arXiv  Detail & Related papers  (2020-11-12T06:57:10Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Efficient quantum processing of ideals in finite rings [1.1724565818034947]
  We show how to find an additive basis representation for I in poly(log |R|) time. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings.
  arXiv  Detail & Related papers  (2009-07-31T23:00:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.