Computing Jacobi's $\theta$ in quasi-linear time

Hugo Labrande (1, 2)

1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
2 University of Calgary

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

Mots clés: Arithmetico-geometric mean; Quasi-linear time complexity; Theta functions; Number theory

Domaines: Théorie des nombres [math.NT]

Hugo Labrande. Computing Jacobi's $\theta$ in quasi-linear time. Mathematics of Computation, 2016, ⟨10.1090/mcom/3245⟩. ⟨hal-01227699v2⟩