Computing Isomorphisms between Products of Supersingular Elliptic Curves

• URL: http://arxiv.org/abs/2503.21535v1
• Date: Thu, 27 Mar 2025 14:26:31 GMT
• Title: Computing Isomorphisms between Products of Supersingular Elliptic Curves
• Authors: Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer,
• Abstract summary: Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields.<n>We present methods for explicitly computing these isomorphisms in time, given the rings of the curves involved.
• Score: 0.9467360130705919
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for explicitly computing these isomorphisms in polynomial time, given the endomorphism rings of the curves involved. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of isomorphisms to solving systems of quadratic and linear equations over the integers derived from norm equations. We develop $\ell$-adic techniques for solving these equations when we have access to a low discriminant subring. Combining these results leads to the description of an efficient probabilistic Las Vegas algorithm for computing the desired isomorphisms. Under GRH, it is proved to run in expected polynomial time.

Related papers

• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution.<n>We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings [0.0]
  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.
  arXiv  Detail & Related papers  (2024-02-07T18:10:54Z)
• The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
  We prove that the endomorphism ring of E can be computed in classical time.<n>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)
• Dynamical chaos in nonlinear Schr\"odinger models with subquadratic power nonlinearity [137.6408511310322]
  We deal with a class of nonlinear Schr"odinger lattices with random potential and subquadratic power nonlinearity. We show that the spreading process is subdiffusive and has complex microscopic organization. The limit of quadratic power nonlinearity is also discussed and shown to result in a delocalization border.
  arXiv  Detail & Related papers  (2023-01-20T16:45:36Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Deep neural networks on diffeomorphism groups for optimal shape reparameterization [44.99833362998488]
  We propose an algorithm for constructing approximations of orientation-preserving diffeomorphisms by composition of elementary diffeomorphisms. The algorithm is implemented using PyTorch, and is applicable for both unparametrized curves and surfaces.
  arXiv  Detail & Related papers  (2022-07-22T15:25:59Z)
• Sum-of-Squares Relaxations for Information Theory and Variational Inference [0.0]
  We consider extensions of the Shannon relative entropy, referred to as $f$-divergences. We derive a sequence of convex relaxations for computing these divergences. We provide more efficient relaxations based on spectral information divergences from quantum information theory.
  arXiv  Detail & Related papers  (2022-06-27T13:22:40Z)
• 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)
• Measuring dissimilarity with diffeomorphism invariance [94.02751799024684]
  We introduce DID, a pairwise dissimilarity measure applicable to a wide range of data spaces. We prove that DID enjoys properties which make it relevant for theoretical study and practical use.
  arXiv  Detail & Related papers  (2022-02-11T13:51:30Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• 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)

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.