Computing Jacobi’s theta in quasi-linear time. (English) Zbl 1430.11167

Labrande, Hugo

Math. Comput. 87, No. 311, 1479-1508 (2018).

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

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