¿Cuál es la probabilidad de que la suma de cuadrados de n números elegidos al azar de$Z_p$ sea un residuo cuadrático mod p?
Es decir, que$a_1$, ..$a_n$ se elija al azar. Entonces, ¿con qué frecuencia$\Sigma_i a^2_i$ es un residuo cuadrático?
Respuesta
¿Demasiados anuncios?
Matt
Puntos
8
La probabilidad depende de la paridad de$n$ y del residuo de$p$ modulo$4$: se puede calcular de forma sencilla utilizando sumas de Gauss.
Sea$n$$2k$ o$2k+1$, y sea$p\equiv r\pmod{4}$ donde$r=\pm 1$. Entonces, asumiendo que no me equivoqué, la probabilidad es igual a PS
Tenga en cuenta que en mi cálculo consideré cero como un residuo cuadrático. Si excluimos cero, la respuesta final se verá ligeramente diferente, con un término principal$$ \frac{p+1}{2p}+\frac{p-1}{2p}(rp)^{-k}. $ como dijo Noam Elkies.
