Computing theta functions in quasi-linear time in genus 2 and above

Hugo Labrande; Emmanuel Thomé

Paper 2016/179

Computing theta functions in quasi-linear time in genus 2 and above

Hugo Labrande and Emmanuel Thomé

Abstract

We outline an algorithm to compute $\theta(z,\tau)$ in genus 2 in quasi-optimal time, borrowing ideas from the algorithm for theta constants and the one for $\theta(z,\tau)$ in genus 1. Our implementation shows a large speedup for precisions as low as a few thousand decimal digits. We also lay out a strategy to generalize this algorithm to genus $g$.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: number theory hyperelliptic curves theta functions
Contact author(s): hugo @ hlabrande fr
History: 2016-02-22: received
Short URL: https://ia.cr/2016/179
License: CC BY

BibTeX

@misc{cryptoeprint:2016/179,
      author = {Hugo Labrande and Emmanuel Thomé},
      title = {Computing theta functions in quasi-linear time in genus 2 and above},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/179},
      year = {2016},
      url = {https://eprint.iacr.org/2016/179}
}