Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Enge, Andreas; Hart, William; Johansson, Fredrik (2016)
Publisher: HAL CCSD
Languages: English
Types: Preprint
Subjects: Mathematics - Number Theory, [MATH.MATH-NT] Mathematics [math]/Number Theory [math.NT]
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 \textgreater{} 0, beating the lower bound of N multiplications required when computing the terms explicitly. These results lead to speed-ups in practice.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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. u-bordeaux.fr/.
    • [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.
    • [11] Andreas Enge. The complexity of class polynomial computation via floating point approximations. Mathematics of Computation, 78(266):1089-1107, 2009.
    • [12] Andreas Enge. Computing modular polynomials in quasi-linear time. Mathematics of Computation, 78(267):1809-1824, 2009.
    • [13] Andreas Enge. CM - Complex multiplication of elliptic curves. INRIA, 0.2.1 edition, March 2015. Distributed under GPL v2+, http://cm.multiprecision.org/.
    • [14] Andreas Enge and François Morain. 164(4):309-341, 2014.
    • [24] Donald Knuth. The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, 3rd edition, 1998.
    • [25] A. M. le Gendre. Essai sur la théorie des nombres. Duprat, Paris, 1797. http://gallica. bnf.fr/ark:/12148/btv1b8626880r.
    • [26] David Mumford. Tata Lectures on Theta I. Birkhäuser, Boston, 1983.
    • [27] David Mumford. Tata Lectures on Theta II - Jacobian theta functions and differential equations. Birkhäuser, Boston, 1984.
    • [28] David Mumford. Tata Lectures on Theta III. Birkhäuser, Boston, 1991.
    • [29] Michael S. Paterson and Larry J. Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal on Computing, 2(1), March 1973.
    • [30] Hans Rademacher. The Fourier coefficients of the modular invariant j(τ ). American Journal of Mathematics, 60(2):501-512, 1938.
    • [31] J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6:64-94, 1962.
    • [32] Reinhard Schertz. Weber's class invariants revisited. Journal de Théorie des Nombres de Bordeaux, 14(1):325-343, 2002.
    • [33] David M. Smith. Efficient multiple-precision evaluation of elementary functions. Mathematics of Computation, 52:131-134, 1989.
    • [34] Heinrich Weber. Lehrbuch der Algebra, volume 3: Elliptische Funktionen und algebraische Zahlen. Vieweg, Braunschweig, 2nd edition, 1908.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

  • BioEntity Site Name

Share - Bookmark

Funded by projects


Cite this article