Counting points on genus-3 hyperelliptic curves with explicit real multiplication

Simon Abelard 1 Pierrick Gaudry 1 Pierre-Jean Spaenlehauer 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperelliptic curve defined over a finite field $Fq$, with explicit real multiplication by an order $Z[η]$ in a totally real cubic field. Our main result states that this algorithm requires an expected number of $O((log q) 6)$ bit-operations, where the constant in the $O()$ depends on the ring $Z[η]$ and on the degrees of polynomials representing the endomorphism $η$. As a proof-of-concept, we compute the zeta function of a curve defined over a 64-bit prime field, with explicit real multiplication by $Z[2 cos(2π/7)$].
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01816256
Contributor : Pierre-Jean Spaenlehauer <>
Submitted on : Thursday, September 20, 2018 - 9:55:03 AM
Last modification on : Thursday, February 14, 2019 - 9:44:04 PM
Long-term archiving on : Friday, December 21, 2018 - 1:09:56 PM

File

RMg3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01816256, version 3

Collections

Citation

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer. Counting points on genus-3 hyperelliptic curves with explicit real multiplication. ANTS-XIII - Thirteenth Algorithmic Number Theory Symposium, Jul 2018, Madison, United States. pp.1--19. ⟨hal-01816256v3⟩

Share

Metrics

Record views

147

Files downloads

164