ABSTRACT.

We describe an algorithm to compute in \( O\!\left(e^{c\sqrt{k\log k}}\right) \) binary operations, for some absolute constant \( c > 0 \), expressions like
\[
\sum_{1 \le n \le 2^{\alpha}}
e^{\frac{2\pi i n^{2}}{2^{k}}}\, n^{a}\,\,\,
{\rm and}
\sum_{1 \le n \le 2^{\alpha}} \sum_{1 \le m \le 2^{\beta}}
e^{\frac{2\pi i n m}{2^{k}}}\, n^{a} m^{b},
\] where \( \alpha, \beta = O(k) \) and \( a,b \) are fixed (small) nonnegative integers. The error terms in these computations are \( O(e^{-ck}) \).

Keywords. Theta series, partial sums, integer factorisation.