Towards computing canonical lifts of ordinary elliptic curves in medium characteristic
| hal.structure.identifier | Université Cheikh Anta Diop de Dakar [Sénégal] [UCAD] | |
| dc.contributor.author | MAIGA, Abdoulaye | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Analyse cryptographique et arithmétique [CANARI] | |
| dc.contributor.author | ROBERT, Damien | |
| dc.date.accessioned | 2024-04-04T02:41:05Z | |
| dc.date.available | 2024-04-04T02:41:05Z | |
| dc.date.created | 2022-03-01 | |
| dc.date.issued | 2022-03-16 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191120 | |
| dc.description.abstractEn | Let $p$ be a prime; using modular polynomial $\Phi_p$, T.~Satoh and al\cite{satoh2000canonical,harley2002,vercau} developed several algorithmsto compute the canonical lift of an ordinary elliptic curve $E$ over$\F_{p^n}$ with $j$-invariant not in $\F_{p^2}$. When $p$ is constant, thebest variant has a complexity $\Otilde(n m)$ to lift $E$ to $p$-adicprecision~$m$. As an application, lifting $E$ to precision $m=O(n)$ allowsto recover its cardinality in time $\Otilde(n^2)$. However, taking $p$ intoaccount the complexity is $\Otilde(p^2 n m)$, so Satoh's algorithm can onlybe applied to small~$p$.We propose in this paper two variants of these algorithms, which do notrely on the modular polynomial, for computing the canonical lift of anordinary curve. Our new method yield a complexity of $\Otilde(p n m)$ tolift at precision~$m$, and even $\Otilde(\sqrt{p} nm)$ when we are provideda rational point of $p$-torsion on the curve. This allows to extend Saoth'spoint counting algorithm to larger~$p$. | |
| dc.description.sponsorship | Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008 | |
| dc.language.iso | en | |
| dc.subject.en | Canonical lift of Elliptic curves | |
| dc.subject.en | Isogeny computation | |
| dc.subject.en | Point counting | |
| dc.title.en | Towards computing canonical lifts of ordinary elliptic curves in medium characteristic | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Mathématiques [math]/Théorie des nombres [math.NT] | |
| dc.subject.hal | Informatique [cs] | |
| 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-03702658 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03702658v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2022-03-16&rft.au=MAIGA,%20Abdoulaye&ROBERT,%20Damien&rft.genre=preprint |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||