Skip to Main content Skip to Navigation
Journal articles

Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus

Abstract : We present a probabilistic Las Vegas algorithm for computing the local zeta function of a genus-g hyperelliptic curve defined over F q with explicit real multiplication (RM) by an order $Z[η]$ in a degree-g totally real number field. It is based on the approaches by Schoof and Pila in a more favorable case where we can split the-torsion into g kernels of endomorphisms, as introduced by Gaudry, Kohel, and Smith in genus 2. To deal with these kernels in any genus, we adapt a technique that the author, Gaudry, and Spaenlehauer introduced to model the-torsion by structured polynomial systems. Applying this technique to the kernels, the systems we obtain are much smaller and so is the complexity of solving them. Our main result is that there exists a constant $c > 0$ such that, for any fixed g, this algorithm has expected time and space complexity $O((log q) c)$ as q grows and the characteristic is large enough. We prove that $c ≤ 9$ and we also conjecture that the result still holds for $c = 7$.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905580
Contributor : Simon Abelard <>
Submitted on : Tuesday, October 15, 2019 - 9:08:46 AM
Last modification on : Tuesday, November 12, 2019 - 3:34:50 PM
Long-term archiving on: : Thursday, January 16, 2020 - 1:28:45 PM

File

rmgen.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Simon Abelard. Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus. Journal of Complexity, Elsevier, In press, ⟨10.1016/j.jco.2019.101440⟩. ⟨hal-01905580v2⟩

Share

Metrics

Record views

146

Files downloads

372