Let $p$ be an odd prime, and let $n=p^k$ where $k\ge 1$. Define $P_n$ to be the set of non-zero polynomials of degree at most $k-1$ and coefficients in $[0,p-1]$. Thus $|P_n|=n-1$.
Now let $f$ be a monic polynomial of degree $k$ whose coefficients are in $[0,p-1]$. Define $$Q_n = \{ g^2 \,\mathrm{mod}\, f \mid g \in P_n \}.$$
Is this true: $f$ is irreducible mod $p$ iff $|Q_n| = (n-1)/2$ and $0\notin Q_n$?
I guess it is true and not hard to prove... The left-to-right direction follows from the fact that $(P_0\cup\{0\})/f$ is a field if $f$ is irreducible mod $p$.
Apologies if anyone wasted their time on this. It is easier than I expected.
Of course $(-g)^2\,\mathrm{mod}\,f=g^2\,\mathrm{mod}\,f$ for any $g$; the question is whether any other coincidences occur.
If $f=h^2$, then $h^2\,\mathrm{mod}\,f=0$ so $0\in Q_n$.
If $f=h\ell$ for $h\ne\ell$ then $(h-\ell)^2\,\mathrm{mod}\,f=(h+\ell)^2\,\mathrm{mod}\,f$.
So in all cases, if $f$ is not irreducible, either 0 appears or $|Q_n|<(n-1)/2$.
I came to this problem because I want to write code to make Paley graphs and I didn't want to implement all the field arithmetic. In particular, I didn't want to implement the usual method for finding an irreducible polynomial. To construct a Paley graph, a list of squares in the field is the only multiplicative operation required. So this lemma gives a method: make lists of squares using random polynomials until a sufficiently long list appears with no zeros. Since around $1/k$ of monic polynomials of degree $k$ are irreducible mod $p$, this will be quite efficient.