Counting Points on Genus 2 Curves with Real Multiplication

P.  Gaudry; D.  Kohel; B.  Smith

Paper 2011/295 Original: eprint.iacr.org/2011/295 ↗

Counting Points on Genus 2 Curves with Real Multiplication

P. Gaudry

D. Kohel

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: Preprint.
History: 2011-06-03: last updated; 2011-06-03: published
Short URL: https://ia.cr/2011/295
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2011/295}
}