The system will be going down for regular maintenance. Please save your work and logout.
Towards computing canonical lifts of ordinary elliptic curves in medium characteristic
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
< Reduce
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Language
en
Document de travail - Pré-publication
This item was published in
2022-03-16
English Abstract
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}$ ...Read more >
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$.Read less <
English Keywords
Canonical lift of Elliptic curves
Isogeny computation
Point counting
ANR Project
Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008
Origin
Hal imported