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

Hugo Labrande 1, 2
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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$.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-01227699
Contributor : Hugo Labrande <>
Submitted on : Thursday, June 2, 2016 - 8:20:14 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Document(s) archivé(s) le : Saturday, September 3, 2016 - 11:40:16 AM

File

theta.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01227699, version 2
  • ARXIV : 1511.04248

Collections

Citation

Hugo Labrande. Computing Jacobi's $\theta$ in quasi-linear time. Mathematics of Computation, American Mathematical Society, 2016. ⟨hal-01227699v2⟩

Share

Metrics

Record views

390

Files downloads

126