Counting Points on Genus 2 Curves with Real Multiplication

DOI10.1007/978-3-642-25385-0_27MaRDI QIDQ3102207zbMATH OpenOpenAlexFDO

Authors Pierrick Gaudry, David Kohel, Benjamin Andrew Smith

Publication date 2 December 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.0661

Mathematics Subject Classification ID

Cryptography (94A60) Applications to coding theory and cryptography of arithmetic geometry (14G50) Computational aspects of algebraic curves (14Q05) Special algebraic curves and curves of low genus (14H45)

Abstract: We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Our new algorithm reduces the complexity of genus 2 point counting over a finite field (F_{q}) of large characteristic from (widetilde{O}(log^8 q)) to (widetilde{O}(log^5 q)). Using our algorithm we compute a 256-bit prime-order Jacobian, suitable for cryptographic applications, and also the order of a 1024-bit Jacobian.

Recommendations

• Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
• Counting points on hyperelliptic curves of genus 2 with real models
• Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication
• Counting points for genus 2 hyperelliptic curves of two special types over finite fields
• Counting points on genus-3 hyperelliptic curves with explicit real multiplication
• Integer Points on Curves of Genus 2 and their Jacobians
• Genus 2 point counting over prime fields
• Counting points on curves over finite fields
• Counting plane curves of any genus
• scientific article; zbMATH DE number 2177420

Cited in

(20)

• Curves, Jacobians, and cryptography
• Advances in Cryptology - EUROCRYPT 2004
• Fast cryptography in genus 2
• The structure of the group of rational points of an abelian variety over a finite field
• Genus 2 point counting over prime fields
• Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
• Improved complexity bounds for counting points on hyperelliptic curves
• Computing cardinalities of \(\mathbb{Q}\)-curve reductions over finite fields
• Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication
• Counting points on genus-3 hyperelliptic curves with explicit real multiplication
• Computing Galois representations of modular abelian surfaces
• Jacobian coordinates on genus 2 curves
• Computing zeta functions of cyclic covers in large characteristic
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
• Bisection for genus 2 curves with a real model
• Hilbert modular polynomials
• Counting points on hyperelliptic curves of genus 2 with real models
• Computing the endomorphism ring of an ordinary abelian surface over a finite field
• Computing isogenies from modular equations in genus two
• Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in \(p\)-adic cohomology

This page was built for publication: Counting Points on Genus 2 Curves with Real Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3102207)