ARPIN, Sarah; CLEMENTS, James; DARTOIS, Pierrick; ERIKSEN, Jonathan Komada; KUTAS, Péter; WESOLOWSKI, Benjamin

doi:10.48550/arXiv.2308.11539

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

ARPIN, Sarah
Universiteit Leiden = Leiden University

CLEMENTS, James
University of Bristol [Bristol]

DARTOIS, Pierrick
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]

Langue

Document de travail - Pré-publication

Ce document a été publié dans

2023

Résumé en anglais

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$.< Réduire

Mots clés en anglais

Number Theory (math.NT)

FOS: Mathematics

URI

https://oskar-bordeaux.fr/handle/20.500.12278/190478

DOI

http://dx.doi.org/10.48550/arXiv.2308.11539

Project ANR

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

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251