Fast computation of the number of solutions to x12+ ··· + xk2 = ¿ (mod n)

Autor: Grau, J.M., Oller-Marcén, A.M.
Rok vydání: 2018
Zdroj: Zaguán. Repositorio Digital de la Universidad de Zaragoza
instname
Popis: In this paper we study the multiplicative function ¿k,¿(n) that counts the number of solutions of the equation x1 2+...+xk 2=¿(modn) in (Z/nZ)k. In particular we give closed explicit formulas for ¿k,¿(ps). This leads to an algorithm with an arithmetic complexity of constant order that improves previous work by Tóth [10] and completes the quadratic case considered by Li and Ouyang in [8].
Databáze: OpenAIRE