ENGE, Andreas; HART, William; JOHANSSON, Fredrik

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

ENGE, Andreas
Lithe and fast algorithmic number theory [LFANT]

HART, William
Fachbereich Mathematik [Kaiserslautern]

JOHANSSON, Fredrik
Lithe and fast algorithmic number theory [LFANT]

Langue

Article de revue

Ce document a été publié dans

Journal of Integer Sequences. 2018, vol. 18, n° 2, p. 1-34

University of Waterloo

Résumé en anglais

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.< Réduire

URI

https://oskar-bordeaux.fr/handle/20.500.12278/193356

Projet Européen

Algorithmic Number Theory in Computer Science

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251