A quasi quadratic time algorithm for hyperelliptic curve point counting

DOI10.1007/s11139-006-0151-6zbMath1166.11021OpenAlexW2085969751MaRDI QIDQ874910

David Lubicz, Reynald Lercier

Publication date: 10 April 2007

Published in: The Ramanujan Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11139-006-0151-6

zbMATH Keywords

CryptographyAGMFinite fieldsHyperelliptic curvesPoint counting algorithms

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) Zeta functions and (L)-functions (11S40) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Related Items

A new proof of a Thomae-like formulafor non hyperelliptic genus 3 curves ⋮ An extension of Kedlaya's algorithm for hyperelliptic curves ⋮ Computing modular correspondences for abelian varieties ⋮ Higher-dimensional 3-adic CM construction ⋮ Generating Genus Two Hyperelliptic Curves over Large Characteristic Finite Fields ⋮ GALOIS THEORY OF THE CANONICAL THETA STRUCTURE ⋮ A Point Counting Algorithm Using Cohomology with Compact Support ⋮ Computing the 2-adic canonical lift of genus 2 curves

Uses Software

• gmp
• Magma
• ZEN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperelliptic cryptosystems
• Factoring polynomials with rational coefficients
• The Magma algebra system. I: The user language
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Tata lectures on theta. I: Introduction and motivation: Theta functions in one variable. Basic results on theta functions in several variables. With the assistance of C. Musili, M. Nori, E. Previato, and M. Stillman
• Theta functions on Riemann surfaces
• Fast computation of canonical lifts of elliptic curves and its application to point counting.
• Endomorphisms of Abelian varieties over finite fields
• On the equations defining Abelian varieties. I-III
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Computing in the Jacobian of a Hyperelliptic Curve
• Computing Zeta Functions of Artin–schreier Curves over Finite Fields
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura