Fast computation of the number of solutions to \(x_1^2 + \cdots + x_k^2 \equiv \lambda \pmod{n}\) (Q669241): Difference between revisions

Let \(k, \lambda \), and \(n\) be positive integers and let \(\rho_{k, \lambda}(n)\) be the number of solutions of the equation \[ x_1^2+\dots+x_k^2 \equiv \lambda \pmod n \] in \( (\mathbb{Z}/n\mathbb{Z})^k\). Identities for \(\rho_{k, \lambda}(n)\) have already been derived using Gauss and Jacobi sums, but they are inefficient because their arithmetic complexity is \( \Theta (n^k)\). More recently, and under some additional restrictions, an efficient algorithm has been provided in [\textit{S. Li} and \textit{Y. Ouyang}, J. Number Theory 187, 41--65 (2018; Zbl 1430.11047)] to compute the number of solutions of the equation \[ \alpha_1x_1^{m_1}+\dots+\alpha_kx_k^{m_k} \equiv \lambda \pmod n \] Using elementary techniques, the authors of the present paper complete the quadratic case considered in the paper above, to give closed explicit formulas for \(\rho_{k, \lambda}(p^s)\) with an arithmetic complexity of constant order. This improves previous work of \textit{L. Tóth} [J. Integer Seq. 17, No. 11, Article 14.11.6, 23 p. (2014; Zbl 1321.11041)].