Computing separable isogenies in quasi-optimal time
| hal.structure.identifier | Institut de Recherche Mathématique de Rennes [IRMAR] | |
| dc.contributor.author | LUBICZ, David | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| hal.structure.identifier | Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | ROBERT, Damien | |
| dc.date.accessioned | 2024-04-04T03:08:11Z | |
| dc.date.available | 2024-04-04T03:08:11Z | |
| dc.date.created | 2014-02-24 | |
| dc.date.issued | 2015 | |
| dc.identifier.issn | 1461-1570 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193508 | |
| dc.description.abstractEn | 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$. | |
| dc.description.sponsorship | Espaces de paramètres pour une arithmétique efficace et une évaluation de la sécurité des courbes - ANR-12-BS01-0010 | |
| dc.description.sponsorship | Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020 | |
| dc.language.iso | en | |
| dc.publisher | London Mathematical Society | |
| dc.title.en | Computing separable isogenies in quasi-optimal time | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1112/S146115701400045X | |
| dc.subject.hal | Mathématiques [math]/Géométrie algébrique [math.AG] | |
| dc.identifier.arxiv | 1402.3628 | |
| dc.description.sponsorshipEurope | Algorithmic Number Theory in Computer Science | |
| bordeaux.journal | LMS Journal of Computation and Mathematics | |
| bordeaux.page | 198-216 | |
| bordeaux.volume | 18 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 1 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00954895 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00954895v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=LMS%20Journal%20of%20Computation%20and%20Mathematics&rft.date=2015&rft.volume=18&rft.issue=1&rft.spage=198-216&rft.epage=198-216&rft.eissn=1461-1570&rft.issn=1461-1570&rft.au=LUBICZ,%20David&ROBERT,%20Damien&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||