Fast computation of the number of solutions to $x_1^2+\cdots +x_k^2\equiv \lambda (\mathrm{mod}n)$

Abstract

In this paper we study the multiplicative function ${\rho }_{k,\lambda }(n)$ that counts the number of incongruent solutions of the equation $x_1^2+\cdots +x_k^2\equiv \lambda (\mathrm{mod}n)$. In particular we give closed explicit formulas for ${\rho }_{k,\lambda }(p^s)$ with a arithmetic complexity of constant order.