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

doi:10.48550/arXiv.2308.11539

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

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]

Idioma

Document de travail - Pré-publication

Este ítem está publicado en

2023

Resumen en inglés

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$.< Leer menos

Palabras clave en inglés

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

Proyecto 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

Orígen

Importado de Hal

Centros de investigación

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