For $N=4k+3$ prime, a solution can easily be found as $x=a^{k+1}$. This is because:
$x^2=a^{2k+2}=a^{2k+1}\cdot a=a^{\frac{N-1}{2}}\cdot a\equiv a\mod N$.
A similar construction can be done for $N=8k+5$.
From http://course1.winona.edu/eerrthum/math347/SquareRoots.pdf, a method is presented for primes of the form $N=8k+1$, but it utilizes an auxiliary number $n$ that is a quadratic nonresidue modulo $N$.
My question is: is there a nontrivial* way to compute a solution to $x^2\equiv a\mod N$ without the use of a known quadratic nonresidue $n$?
*without checking every positive integer less than $N$ etc.