×

zbMATH — the first resource for mathematics

Computing Jacobi’s theta in quasi-linear time. (English) Zbl 1430.11167
Summary: 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\).

MSC:
11Y16 Number-theoretic algorithms; complexity
14Q20 Effectivity, complexity and computational aspects of algebraic geometry
14Q05 Computational aspects of algebraic curves
14H42 Theta functions and curves; Schottky problem
14K25 Theta functions and abelian varieties
14H81 Relationships between algebraic curves and physics
11-04 Software, source code, etc. for problems pertaining to number theory
Software:
MPC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borwein, Jonathan M.; Borwein, Peter B., Pi and the AGM, Canadian Mathematical Society Series of Monographs and Advanced Texts, xvi+414 pp., (1987), John Wiley and Sons, Inc., New York · Zbl 0903.11001
[2] Bost, Jean-Beno\^\i t.; Mestre, Jean-Fran\ccois, Moyenne arithm\'etico-g\'eom\'etrique et p\'eriodes des courbes de genre \(1\) et \(2\), Gaz. Math., No. 38, 36-64, (1988) · Zbl 0682.14031
[3] CossetPhd R. Cosset, \emph Applications des fonctions th\^eta \`a la cryptographie sur courbes hyperelliptiques., Ph.D. thesis, Universit\'e Henri Poincar\'e-Nancy I, 2011.
[4] Cox, David A., The arithmetic-geometric mean of Gauss, Enseign. Math. (2), 30, 3-4, 275-330, (1984) · Zbl 0583.33002
[5] Cremona, John E.; Thongjunthug, Thotsaphon, The complex AGM, periods of elliptic curves over \(\mathbb{C}\) and complex elliptic logarithms, J. Number Theory, 133, 8, 2813-2841, (2013) · Zbl 1301.11055
[6] DupontPhd R. Dupont, \emph Moyenne arithm\'etico-g\'eom\'etrique, suites de Borchardt et applications, Ph.D. thesis, \'Ecole polytechnique, Palaiseau, 2006, <span class=”texttt”>h</span>ttp://www.lix.polytechnique.fr/Labo/\linebreak <span class=”texttt”>R</span>egis.Dupont/these_soutenance.pdf
[7] Dupont, R\'egis, Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comp., 80, 275, 1823-1847, (2011) · Zbl 1221.65075
[8] Enge, Andreas, The complexity of class polynomial computation via floating point approximations, Math. Comp., 78, 266, 1089-1107, (2009) · Zbl 1208.11136
[9] MPC A. Enge, M. Gastineau, P. Th\'eveny, and P. Zimmerman, \emph GNU MPC – A library for multiprecision complex arithmetic with exact rounding, INRIA, September 2012, Release 1.0.1, http://mpc.multiprecision.org/.
[10] Enge, Andreas; Thom\'e, Emmanuel, Computing class polynomials for abelian surfaces, Exp. Math., 23, 2, 129-145, (2014) · Zbl 1293.11107
[11] absolutelossofprec Hugo Labrande, \emph Absolute error in complex fixed-point arithmetic, 2015, available at <span class=”texttt”>h</span>ttp://www.hlabrande.fr/pubs/absolutelossofprecision.pdf.
[12] Luther, Wolfram; Otten, Werner, Reliable computation of elliptic functions, J. Univ. Comp. Sci., 4, 1, 25-33, (1998) · Zbl 0965.65046
[13] Mumford, David, Tata Lectures on Theta. I, Progress in Mathematics 28, xiii+235 pp., (1983), Birkh\"auser Boston, Inc., Boston, MA
[14] Vall\'ee, Brigitte, Gauss’ algorithm revisited, J. Algorithms, 12, 4, 556-572, (1991) · Zbl 0779.11065
[15] Weber H. Weber, \emph Lehrbuch der algebra, Druck und verlag Fr. Vieweg & Sohn, 1921. \endbiblist
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.