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

**Category / Keywords: **public-key cryptography / number theory, elliptic curve cryptosystem, theta function

**Date: **received 12 Nov 2015, last revised 2 Jun 2016

**Contact author: **hugo at hlabrande fr

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20160602:182353 (All versions of this report)

**Short URL: **ia.cr/2015/1104

[ Cryptology ePrint archive ]