Skip to Main content Skip to Navigation
New interface
Conference papers

Counting Points on Genus 2 Curves with Real Multiplication

Pierrick Gaudry 1 David Kohel 2 Benjamin Smith 3 
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Benjamin Smith Connect in order to contact the contributor
Submitted on : Friday, June 3, 2011 - 1:35:25 PM
Last modification on : Wednesday, February 2, 2022 - 4:30:56 PM
Long-term archiving on: : Sunday, September 4, 2011 - 2:22:47 AM


Files produced by the author(s)



Pierrick Gaudry, David Kohel, Benjamin Smith. Counting Points on Genus 2 Curves with Real Multiplication. ASIACRYPT 2011, International Association for Cryptologic Research, Dec 2011, Seoul, South Korea. pp.504-519, ⟨10.1007/978-3-642-25385-0_27⟩. ⟨inria-00598029⟩



Record views


Files downloads