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