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
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00598029
Contributor : Benjamin Smith <>
Submitted on : Friday, June 3, 2011 - 1:35:25 PM
Last modification on : Wednesday, April 3, 2019 - 1:23:03 AM
Document(s) archivé(s) le : Sunday, September 4, 2011 - 2:22:47 AM

Files

paper.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

844

Files downloads

263