Paper 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.

Note: Corrected a proof in Section 3.4; added proof that the Jacobian is invertible.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
number theoryelliptic curve cryptosystemtheta function
Contact author(s)
hugo @ hlabrande fr
History
2016-06-02: revised
2015-11-14: received
See all versions
Short URL
https://ia.cr/2015/1104
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2015/1104}},
      url = {https://eprint.iacr.org/2015/1104}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.