Short addition sequences for theta functions
From MaRDI portal
Publication:4637128
Abstract: The main step in numerical evaluation of classical Sl2 (Z) modular forms and elliptic functions is to compute the sum of the first N nonzero terms in the sparse q-series belonging to the Dedekind eta function or the Jacobi theta constants. We construct short addition sequences to perform this task using N + o(N) multiplications. Our constructions rely on the representability of specific quadratic progressions of integers as sums of smaller numbers of the same kind. For example, we show that every generalised pentagonal number c 5 can be written as c = 2a + b where a, b are smaller generalised pentagonal numbers. We also give a baby-step giant-step algorithm that uses O(N/ log r N) multiplications for any r > 0, beating the lower bound of N multiplications required when computing the terms explicitly. These results lead to speed-ups in practice.
Recommendations
- Computing Jacobi's theta in quasi-linear time
- Fast evaluation of modular functions using Newton iterations and the AGM
- Computing the truncated theta function via Mordell integral
- Computing theta functions in quasi-linear time in genus two and above
- A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals
Cites work
- A Heuristic Asymptotic Formula Concerning the Distribution of Prime Numbers
- Addition Chain Methods for the Evaluation of Specific Polynomials
- Advanced Topics in Computional Number Theory
- Approximate formulas for some functions of prime numbers
- Bilinear pairings on elliptic curves
- Computing modular polynomials in quasi-linear time
- Computing Sequences with Addition Chains
- Constructing elliptic curves over finite fields using double eta-quotients
- Efficient Multiple-Precision Evaluation of Elementary Functions
- Evaluating parametric holonomic sequences using rectangular splitting
- Fast evaluation of modular functions using Newton iterations and the AGM
- Fast multiplication and its applications
- Generalised Weber functions
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- scientific article; zbMATH DE number 5903192 (Why is no real title available?)
- scientific article; zbMATH DE number 3916389 (Why is no real title available?)
- scientific article; zbMATH DE number 4055695 (Why is no real title available?)
- scientific article; zbMATH DE number 45834 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- Singular values of multiple eta-quotients for ramified primes
- Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura
- Tata lectures on theta. III
- The complexity of class polynomial computation via floating point approximations
- The number of representations of a number by various forms involving triangles, squares, pentagons and octagons
- Weber's class invariants revisited
Cited in
(5)
This page was built for publication: Short addition sequences for theta functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637128)
