Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

Computing Jacobi's theta in quasi-linear time


Author: 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
Published electronically: November 1, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Jonathan M. Borwein and Peter B. Borwein, Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity; A Wiley-Interscience Publication, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley and Sons, Inc., New York, 1987. MR 877728
  • [2] 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. No. 38 (1988), 36-64 (French). MR 970659
  • [3] R. Cosset, Applications des fonctions thêta à la cryptographie sur courbes hyperelliptiques., Ph.D. thesis, Université Henri Poincaré-Nancy I, 2011.
  • [4] David A. Cox, The arithmetic-geometric mean of Gauss, Enseign. Math. (2) 30 (1984), no. 3-4, 275-330. MR 767905
  • [5] John E. Cremona and Thotsaphon Thongjunthug, The complex AGM, periods of elliptic curves over $ \mathbb{C}$ and complex elliptic logarithms, J. Number Theory 133 (2013), no. 8, 2813-2841. MR 3045217
  • [6] 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
  • [7] Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comp. 80 (2011), no. 275, 1823-1847. MR 2785482
  • [8] Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089-1107. MR 2476572
  • [9] 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/.
  • [10] Andreas Enge and Emmanuel Thomé, Computing class polynomials for abelian surfaces, Exp. Math. 23 (2014), no. 2, 129-145. MR 3223768
  • [11] Hugo Labrande, Absolute error in complex fixed-point arithmetic, 2015, available at http://www.hlabrande.fr/pubs/absolutelossofprecision.pdf.
  • [12] Wolfram Luther and Werner Otten, Reliable computation of elliptic functions, J. Univ. Comp. Sci. 4 (1998), no. 1, 25-33. SCAN-97 (Lyon). MR 1661836
  • [13] David Mumford, , , , and Tata Lectures on Theta. I, Progress in Mathematics, vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. MR 688651
  • [14] Brigitte Vallée, Gauss' algorithm revisited, J. Algorithms 12 (1991), no. 4, 556-572. MR 1130316
  • [15] H. Weber, Lehrbuch der algebra, Druck und verlag Fr. Vieweg & Sohn, 1921.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11-04, 14H42, 14K25, 14H81, 14H82

Retrieve articles in all journals with MSC (2010): 11-04, 14H42, 14K25, 14H81, 14H82


Additional Information

Hugo Labrande
Affiliation: INRIA Lorraine – projet CARAMBA, 615 rue du jardin botanique, 54602 Villers-les-Nancy Cedex, France
Email: hugo@hlabrande.fr

DOI: https://doi.org/10.1090/mcom/3245
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
Article copyright: © Copyright 2017 by Hugo Labrande

American Mathematical Society