Computing Jacobi’s theta in quasi-linear time
HTML articles powered by AMS MathViewer
- by Hugo Labrande PDF
- Math. Comp. 87 (2018), 1479-1508
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 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$.References
- Jonathan M. Borwein and Peter B. Borwein, Pi and the AGM, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1987. A study in analytic number theory and computational complexity; A Wiley-Interscience Publication. MR 877728
- Jean-Benoît Bost and Jean-François Mestre, Moyenne arithmético-géométrique et périodes des courbes de genre $1$ et $2$, Gaz. Math. 38 (1988), 36–64 (French). MR 970659
- R. Cosset, Applications des fonctions thêta à la cryptographie sur courbes hyperelliptiques., Ph.D. thesis, Université Henri Poincaré-Nancy I, 2011.
- David A. Cox, The arithmetic-geometric mean of Gauss, Enseign. Math. (2) 30 (1984), no. 3-4, 275–330. MR 767905
- John E. Cremona and Thotsaphon Thongjunthug, The complex AGM, periods of elliptic curves over $\Bbb {C}$ and complex elliptic logarithms, J. Number Theory 133 (2013), no. 8, 2813–2841. MR 3045217, DOI 10.1016/j.jnt.2013.02.002
- R. Dupont, Moyenne arithmético-géométrique, suites de Borchardt et applications, Ph.D. thesis, École polytechnique, Palaiseau, 2006, http://www.lix.polytechnique.fr/Labo/ Regis.Dupont/these_soutenance.pdf
- Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comp. 80 (2011), no. 275, 1823–1847. MR 2785482, DOI 10.1090/S0025-5718-2011-01880-6
- Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572, DOI 10.1090/S0025-5718-08-02200-X
- A. Enge, M. Gastineau, P. Théveny, and P. Zimmerman, GNU MPC – A library for multiprecision complex arithmetic with exact rounding, INRIA, September 2012, Release 1.0.1, http://mpc.multiprecision.org/.
- Andreas Enge and Emmanuel Thomé, Computing class polynomials for abelian surfaces, Exp. Math. 23 (2014), no. 2, 129–145. MR 3223768, DOI 10.1080/10586458.2013.878675
- Hugo Labrande, Absolute error in complex fixed-point arithmetic, 2015, available at http://www.hlabrande.fr/pubs/absolutelossofprecision.pdf.
- Wolfram Luther and Werner Otten, Reliable computation of elliptic functions, J.UCS 4 (1998), no. 1, 25–33. SCAN-97 (Lyon). MR 1661836
- David Mumford, Tata lectures on theta. I, Progress in Mathematics, vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR 688651, DOI 10.1007/978-1-4899-2843-6
- Brigitte Vallée, Gauss’ algorithm revisited, J. Algorithms 12 (1991), no. 4, 556–572. MR 1130316, DOI 10.1016/0196-6774(91)90033-U
- H. Weber, Lehrbuch der algebra, Druck und verlag Fr. Vieweg & Sohn, 1921.
Additional Information
- Hugo Labrande
- Affiliation: INRIA Lorraine – projet CARAMBA, 615 rue du jardin botanique, 54602 Villers-les-Nancy Cedex, France
- MR Author ID: 989660
- Email: hugo@hlabrande.fr
- Received by editor(s): November 13, 2015
- Received by editor(s) in revised form: June 2, 2016, and November 22, 2016
- Published electronically: November 1, 2017
- © Copyright 2017 by Hugo Labrande
- Journal: Math. Comp. 87 (2018), 1479-1508
- MSC (2010): Primary 11-04, 14H42, 14K25; Secondary 14H81, 14H82
- DOI: https://doi.org/10.1090/mcom/3245
- MathSciNet review: 3766395