The system will be going down for regular maintenance. Please save your work and logout.
Finding Orientations of Supersingular Elliptic Curves and Quaternion Orders
DARTOIS, Pierrick
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
See more >
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
DARTOIS, Pierrick
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
ERIKSEN, Jonathan Komada
Norwegian University of Science and Technology = Norges Teknisk-Naturvitenskapelige Universitet = Norjan teknis-luonnontieteellinen yliopisto [NTNU]
Norwegian University of Science and Technology = Norges Teknisk-Naturvitenskapelige Universitet = Norjan teknis-luonnontieteellinen yliopisto [NTNU]
KUTAS, Péter
Eötvös Loránd Tudományegyetem = Eötvös Loránd University [Budapest] [ELTE]
University of Birmingham [Birmingham]
Eötvös Loránd Tudományegyetem = Eötvös Loránd University [Budapest] [ELTE]
University of Birmingham [Birmingham]
WESOLOWSKI, Benjamin
Lithe and fast algorithmic number theory [LFANT]
Unité de Mathématiques Pures et Appliquées [UMPA-ENSL]
Centre National de la Recherche Scientifique [CNRS]
< Reduce
Lithe and fast algorithmic number theory [LFANT]
Unité de Mathématiques Pures et Appliquées [UMPA-ENSL]
Centre National de la Recherche Scientifique [CNRS]
Language
en
Document de travail - Pré-publication
This item was published in
2023
English Abstract
Orientations of supersingular elliptic curves encode the information of an endomorphism of the curve. Computing the full endomorphism ring is a known hard problem, so one might consider how hard it is to find one such ...Read more >
Orientations of supersingular elliptic curves encode the information of an endomorphism of the curve. Computing the full endomorphism ring is a known hard problem, so one might consider how hard it is to find one such orientation. We prove that access to an oracle which tells if an elliptic curve is $\mathfrak{O}$-orientable for a fixed imaginary quadratic order $\mathfrak{O}$ provides non-trivial information towards computing an endomorphism corresponding to the $\mathfrak{O}$-orientation. We provide explicit algorithms and in-depth complexity analysis. We also consider the question in terms of quaternion algebras. We provide algorithms which compute an embedding of a fixed imaginary quadratic order into a maximal order of the quaternion algebra ramified at $p$ and $\infty$. We provide code implementations in Sagemath which is efficient for finding embeddings of imaginary quadratic orders of discriminants up to $O(p)$, even for cryptographically sized $p$.Read less <
English Keywords
Number Theory (math.NT)
FOS: Mathematics
ANR Project
Méthodes pour les variétés abéliennes de petite dimension - ANR-20-CE40-0013
Post-quantum padlock for web browser - ANR-22-PETQ-0008
Post-quantum padlock for web browser - ANR-22-PETQ-0008
Origin
Hal imported
