2018/10/25 by Simon Abelard, Abelard, Simon
Mathematics · Computer Science · #Algebraic Geometry and Number Theory #Polynomial and algebraic computation #Analytic Number Theory Research
paper · pdf · doi:10.48550/arxiv.1810.11068
We present a probabilistic Las Vegas algorithm for computing the local zeta\nfunction of a genus-g hyperelliptic curve defined over mathbb Fq with\nexplicit real multiplication (RM) by an order Z[\η] in a degree-g\ntotally real number field.\n It is based on the approaches by Schoof and Pila in a more favorable case\nwhere we can split the \ℓ-torsion into g kernels of endomorphisms, as\nintroduced by Gaudry, Kohel, and Smith in genus 2. To deal with these kernels\nin any genus, we adapt a technique that the author, Gaudry, and Spaenlehauer\nintroduced to model the \ℓ-torsion by structured polynomial systems.\nApplying this technique to the kernels, the systems we obtain are much smaller\nand so is the complexity of solving them.\n Our main result is that there exists a constant c>0 such that, for any\nfixed g, this algorithm has expected time and space complexity O((\log\nq)c) as q grows and the characteristic is large enough. We prove that\nc\≤ 9 and we also conjecture that the result still holds for c=7.\n