Computing separable isogenies in quasi-optimal time
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
< Réduire
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
Langue
en
Article de revue
Ce document a été publié dans
LMS Journal of Computation and Mathematics. 2015, vol. 18, n° 1, p. 198-216
London Mathematical Society
Résumé en anglais
Let $A$ be an abelian variety of dimension $g$ together with a principal polarization $\phi: A \rightarrow \hat{A}$ defined over a field $k$. Let $\ell$ be an odd integer prime to the characteristic of $k$ and let $K$ be ...Lire la suite >
Let $A$ be an abelian variety of dimension $g$ together with a principal polarization $\phi: A \rightarrow \hat{A}$ defined over a field $k$. Let $\ell$ be an odd integer prime to the characteristic of $k$ and let $K$ be a subgroup of $A[\ell]$ which is maximal isotropic for the Riemann form associated to $\phi$. We suppose that $K$ is defined over $k$ and let $B=A/K$ be the quotient abelian variety together with a polarization compatible with $\phi$. Then $B$, as a polarized abelian variety, and the isogeny $f:A\rightarrow B$ are also defined over $k$. In this paper, we describe an algorithm that takes as input a theta null point of $A$ and a polynomial system defining $K$ and outputs a theta null point of $B$ as well as formulas for the isogeny $f$. We obtain a complexity of $\tilde{O}(\ell^{\frac{rg}{2}})$ operations in $k$ where $r=2$ (resp. $r=4$) if $\ell$ is a sum of two squares (resp. if $\ell$ is a sum of four squares) which constitutes an improvement over the algorithm described in [7]. We note that the algorithm is quasi-optimal if $\ell$ is a sum of two squares since its complexity is quasi-linear in the degree of $f$.< Réduire
Projet Européen
Algorithmic Number Theory in Computer Science
Project ANR
Espaces de paramètres pour une arithmétique efficace et une évaluation de la sécurité des courbes - ANR-12-BS01-0010
Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
Origine
Importé de halUnités de recherche