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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
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.
Type de document :
Communication dans un congrès
Lee, Dong Hoon and Wang, Xiaoyun. ASIACRYPT 2011, Dec 2011, Seoul, South Korea. Springer, 7073, pp.504-519, 2011, Lecture Notes in Computer Science; Advances in Cryptology -- ASIACRYPT 2011. <10.1007/978-3-642-25385-0_27>
Liste complète des métadonnées


https://hal.inria.fr/inria-00598029
Contributeur : Benjamin Smith <>
Soumis le : vendredi 3 juin 2011 - 13:35:25
Dernière modification le : jeudi 9 février 2017 - 15:11:18
Document(s) archivé(s) le : dimanche 4 septembre 2011 - 02:22:47

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pierrick Gaudry, David Kohel, Benjamin Smith. Counting Points on Genus 2 Curves with Real Multiplication. Lee, Dong Hoon and Wang, Xiaoyun. ASIACRYPT 2011, Dec 2011, Seoul, South Korea. Springer, 7073, pp.504-519, 2011, Lecture Notes in Computer Science; Advances in Cryptology -- ASIACRYPT 2011. <10.1007/978-3-642-25385-0_27>. <inria-00598029>

Partager

Métriques

Consultations de
la notice

455

Téléchargements du document

185