Finding Orientations of Supersingular Elliptic Curves and Quaternion Orders
| hal.structure.identifier | Universiteit Leiden = Leiden University | |
| dc.contributor.author | ARPIN, Sarah | |
| hal.structure.identifier | University of Bristol [Bristol] | |
| dc.contributor.author | CLEMENTS, James | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Analyse cryptographique et arithmétique [CANARI] | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| dc.contributor.author | DARTOIS, Pierrick | |
| hal.structure.identifier | Norwegian University of Science and Technology [NTNU] | |
| dc.contributor.author | ERIKSEN, Jonathan Komada | |
| hal.structure.identifier | Eötvös Loránd University [ELTE] | |
| hal.structure.identifier | University of Birmingham [Birmingham] | |
| dc.contributor.author | KUTAS, Péter | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| hal.structure.identifier | Unité de Mathématiques Pures et Appliquées [UMPA-ENSL] | |
| hal.structure.identifier | Centre National de la Recherche Scientifique [CNRS] | |
| dc.contributor.author | WESOLOWSKI, Benjamin | |
| dc.date.accessioned | 2024-04-04T02:33:26Z | |
| dc.date.available | 2024-04-04T02:33:26Z | |
| dc.date.issued | 2023 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190478 | |
| dc.description.abstractEn | 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$. | |
| dc.description.sponsorship | Méthodes pour les variétés abéliennes de petite dimension - ANR-20-CE40-0013 | |
| dc.description.sponsorship | Post-quantum padlock for web browser - ANR-22-PETQ-0008 | |
| dc.language.iso | en | |
| dc.rights.uri | http://creativecommons.org/licenses/by/ | |
| dc.subject.en | Number Theory (math.NT) | |
| dc.subject.en | FOS: Mathematics | |
| dc.title.en | Finding Orientations of Supersingular Elliptic Curves and Quaternion Orders | |
| dc.type | Document de travail - Pré-publication | |
| dc.identifier.doi | 10.48550/arXiv.2308.11539 | |
| dc.subject.hal | Mathématiques [math] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-04186188 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-04186188v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2023&rft.au=ARPIN,%20Sarah&CLEMENTS,%20James&DARTOIS,%20Pierrick&ERIKSEN,%20Jonathan%20Komada&KUTAS,%20P%C3%A9ter&rft.genre=preprint |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||