Computing Dirichlet character sums to a power-full modulus (Q401979)

This paper provides a practical method for computing Dirichlet character sums \(L(s, \chi)\), where \(\chi\) is a character modulo \(q\). This method is particularly efficient when \(q\) is smooth enough (\textit{the radical of \(q\) is small enough when compared with \(q\)}) or a \textit{power-full modulus}, that is, when \(q\) is a prime power or when the number of its prime factors is low. Here is the main result: There are absolute constants \(A_1, A_2, \dots, A_5, \kappa_1, \kappa_2, \kappa_3\) such that for any real number \(\lambda\), any complex number \(s\) with \(1/2 \leq \mathrm{Re}(s) \leq 1\), any positive integer \(q = p_1^{\alpha_1}\dots p_h^{\alpha_h}\) (with distinct primes \(p_i\)) and any given character \(\chi\) mod \(q\), the value of the Dirichlet \(L\)-function \(L(s, \chi)\) can be computed to within \(q^{-1}(| s | + 1)^{-\lambda}\) using \(\leq A_1p_1^{\left\lceil \alpha_1/3\right\rceil}\dots p_h^{\left\lceil \alpha_h/3\right\rceil}(| s | + 1)^{1/3}(\lambda + 1)^{\kappa_1} \log^{\kappa_1}(q(| s | + 1))\) operations on numbers of \(\leq A_2(\lambda + 1)^4 \log^4(q(| s | + 1))\) bits, provided a precomputation, that depends on \(q\) only, costing \(A_3(p_1 + \dots + p_h)\log^{\kappa_2} q\) operations on numbers of \(\leq A_4 \log q\) bits, and requiring \(\leq A_5(p_1\dots + p_h)\log^{\kappa_3}q\) bits of storage.