Cryptology ePrint Archive: Report 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.

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

Discussion forum: Show discussion | Start new discussion