Computing Jacobi's \theta in quasi-linear time

Hugo Labrande

Paper 2015/1104 Original: eprint.iacr.org/2015/1104 ↗

Computing Jacobi's \theta in quasi-linear time

Hugo Labrande

Abstract

Jacobi's \theta function has numerous applications in mathematics and computer science; a naive algorithm allows the computation of \theta(z, \tau), for z, \tau verifying certain conditions, with precision P in O(M(P) \sqrt{P}) bit operations, where M(P) denotes the number of operations needed to multiply two complex P-bit numbers. We generalize an algorithm which computes specific values of the \theta function (the theta-constants) in asymptotically faster time; this gives us an algorithm to compute \theta(z, \tau) with precision P in O(M(P) log P) bit operations, for any \tau \in F and z reduced using the quasi-periodicity of \theta.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2016-06-02: last updated; 2015-11-14: published
Short URL: https://ia.cr/2015/1104
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2015/1104,
      author = {Hugo Labrande},
      title = {Computing Jacobi's \theta in quasi-linear time},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1104},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1104}
}