Below is little-known general yet simple answer to your question about nontrivial sqrts $\rm (mod\ m)\:$.
Theorem $ $ We can quickly factor $\rm m>1\,$ given a polynomial with more roots mod $\rm\, m\,$ than its degree. For if $\rm\bmod m,\;$ the polynomial $\rm\, f(x)\ne 0\,$ has degree $\rm\,n\,$ but has $\rm\,n+1 \,$ distinct roots $\rm\,r_{\,i}\,$ then one of $\rm\;gcd(m,\,r_{\,i} - r_{\,j}),\; i\ne j \,$ must yield a proper factor of $\rm\,m.\,$ For if that failed, then all of the gcds must be improper hence $1,\,$ not $\rm\;m \;$ since $\rm\; i\ne j\;\Rightarrow\; r_{\,i} \not\equiv r_{\,j}\ (mod\ m).\,$ Now an induction using the Factor Theorem as here yields $\rm\;f(x) = (x-r_1)\cdots(x-r_{n+1})\; g(x),\;\; g(x) \ne 0 \;\;$ contra $\rm\,\deg\, f = n.$
Example $\rm\;(deg\ f = 1)\;\,$ Suppose, modulo $\rm\,m,\,$ that $\rm\; 0 \,\ne\, f \,=\, a\,x\;$ has a "nontrivial" root $\rm\, b\ne 0.\,$ Then $\,\rm gcd(m,b)\,$ is a proper factor of $\rm\, m.\ $ More directly: $\rm\; m\mid ab,\ m\nmid a,b \;\Rightarrow\; gcd(m,b)\;$ is a proper factor of $\rm\,m\,,\,$ i.e. $\rm\, m\,$ fails the Prime Divisor Property $\rm\,\Rightarrow m\,$ is "constructively" composite.
Example $\rm\;(deg\ f = 2)\;\,$ Suppose, modulo $\rm\,m\,$, $\rm\; x^2 = 1\,$ has a "nontrivial" square root $\rm\, b\ne \pm1.\,$ Then $\;\rm gcd(m,b\pm 1)\;$ yields a proper factor of $\rm\, m\,$ when $\rm\, m\,$ is odd. This idea lies at the heart of many integer factorization algorithms.
The above proof easily extends to yield a proof of the following
Theorem $ $ Ring $\rm\, R$ is a domain $\iff$ every $\rm\, 0 \ne f(x)\in R[x]\,$ has at most $\rm\, deg\ f(x)\,$ roots in $\rm R$
Proof $\ $ $(\Rightarrow)\;$ Employ induction on the polynomial degree, as in the proof of the above Theorem. $(\Leftarrow)\ \ $ If $\rm\; a \ne 0\;$ then the polynomial $\rm\, a\,x\,$ has only the root $\rm\; x = 0,\,$ hence $\rm\ ab = 0 \ \Rightarrow\ b = 0,\,$ therefore $\rm\, R\,$ has no zero divisors.