International Association
for Cryptologic Research

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.