2 added 193 characters in body

The probability depends on the parity of $n$ and the residue of $p$ modulo $4$: it can be calculated in a straightforward way using Gauss sums.

Let $n$ be $2k$ or $2k+1$, and let $p\equiv r\pmod{4}$ where $r=\pm 1$. Then, assuming I made no mistake, the probability equals $$\frac{p+1}{2p}+\frac{p-1}{2p}(rp)^{-k}.$$

Note that in my calculation I regarded zero as a quadratic residue. If we exclude zero then the final answer will look slightly different, with a main term $\frac{p-1}{2p}$ as Noam Elkies said.

1

The probability depends on the parity of $n$ and the residue of $p$ modulo $4$: it can be calculated in a straightforward way using Gauss sums.

Let $n$ be $2k$ or $2k+1$, and let $p\equiv r\pmod{4}$ where $r=\pm 1$. Then, assuming I made no mistake, the probability equals $$\frac{p+1}{2p}+\frac{p-1}{2p}(rp)^{-k}.$$