Short addition sequences for theta functions

Article, Preprint English OPEN
Enge , Andreas ; Hart , William ; Johansson , Fredrik (2018)
  • Publisher: University of Waterloo
  • Subject: [ MATH.MATH-NT ] Mathematics [math]/Number Theory [math.NT] | Mathematics - Number Theory

International audience; 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.
  • References (31)
    31 references, page 1 of 4

    [1] Paul T. Bateman and Roger A. Horn. A heuristic asymptotic formula concerning the distribution of prime numbers. Mathematics of Computation, 16(79):363-367, 1962.

    [2] Karim Belabas et al. PARI/GP. Bordeaux, 2.7.5 edition, November 2015. http://pari.math.

    [3] Daniel J. Bernstein. Fast multiplication and its applications. Algorithmic Number Theory, 44:325-384, 2008.

    [4] D. V. Chudnovsky and G. V. Chudnovsky. Approximations and complex multiplication according to Ramanujan. In Ramanujan Revisited, pages 375-472. Academic Press, 1988. Proceedings of the Centenary Conference, University of Illinois at Urbana-Champaign, June 1-5, 1987.

    [5] Henri Cohen. Advanced Topics in Computational Number Theory, volume 193 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2000.

    [6] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete mathematics and its applications. Chapman & Hall/CRC, Boca Raton, 2006.

    [7] David A. Cox. Primes of the Form x2 + ny2 - Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, New York, 1989.

    [8] David Dobkin and Richard J. Lipton. Addition chain methods for the evaluation of specific polynomials. SIAM Journal on Computing, 9(1):121-125, 1980.

    [9] Peter Downey, Benton Leong, and Ravi Sethi. Computing sequences with addition chains. SIAM Journal on Computing, 10(3):638-646, August 1981.

    [10] Régis Dupont. Fast evaluation of modular functions using Newton iterations and the AGM. Mathematics of Computation, 80(275):1823-1847, 2011.

  • Similar Research Results (2)
  • Metrics
    No metrics available
Share - Bookmark