Paper 2011/295

Counting Points on Genus 2 Curves with Real Multiplication

P. Gaudry, D. Kohel, and B. Smith

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 $GF(q)$ of large characteristic from $\sO(\log^8 q)$ to $\sO(\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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
pierrick gaudry @ loria fr
History
2011-06-03: received
Short URL
https://ia.cr/2011/295
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/295,
      author = {P.  Gaudry and D.  Kohel and B.  Smith},
      title = {Counting Points on Genus 2 Curves with Real Multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2011/295},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/295}},
      url = {https://eprint.iacr.org/2011/295}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.