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

Hugo Labrande 1, 2, 3, *
* Auteur correspondant
2 CARAMEL - Cryptology, Arithmetic: Hardware and Software
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(\mathcal{M}(P) \sqrt{P})$ bit operations, where $\mathcal{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 \textit{theta-constants}) in asymptotically faster time; this gives us an algorithm to compute $\theta(z, \tau)$ with precision $P$ in $O(\mathcal{M}(P) \log P)$ bit operations, for any $\tau \in \mathcal{F}$ and $z$ reduced using the quasi-periodicity of $\theta$.
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01227699
Contributeur : Hugo Labrande <>
Soumis le : vendredi 13 novembre 2015 - 05:58:26
Dernière modification le : mercredi 8 juin 2016 - 01:05:45
Document(s) archivé(s) le : dimanche 14 février 2016 - 10:21:29

Fichiers

theta.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Hugo Labrande. Computing Jacobi's $\theta$ in quasi-linear time. 2015. <hal-01227699v1>

Partager

Métriques

Consultations de
la notice

266

Téléchargements du document

34