Counting Points on Genus 2 Curves with Real MultiplicationReport as inadecuate

Counting Points on Genus 2 Curves with Real Multiplication - Download this document for free, or read online. Document in PDF available to download.

1 CARAMEL - Cryptology, Arithmetic: Hardware and Software Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry 2 IML - Institut de mathématiques de Luminy 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.

Author: Pierrick Gaudry - David Kohel - Benjamin Smith -



Related documents