number theory - Least quadratic non residue algorithm

I am trying to implement Tonelli-Shanks algorithm and at one of the steps I have to find the least quadratic non residue. I've searched the web for a while for some kind of algorithm but so far I've seen only paper with lot's of math behind them.
Are there any algorithms for finding least non negative residues our there? Or could someone advise me a paper with good explanations and a couple of examples so I can formalize the algorithm myself?

Answer

I would not worry about it. The least quadratic non-residue modulo a fixed prime $q$ is also a prime, so just check the primes $2,3,5,7,11,13,17, \ldots$ in order until the Legendre symbol says you have a non-residue. The important thing is that the first non-residue is really, really small compared to the prime itself. See OEIS.

Oh, why is the first nonresidue prime? Call the prime $q$ and the first nonresidue $N.$ Since $1$ is always a residue, we have $N > 1.$ Since exactly half the numbers from $1$ to $q-1$ are residues, half nonresidues, we know $N < q.$ If $N$ were also composite, we would have $N = ab$ with $1 < a,b < N.$ Since $N$ is the smallest nonresidue, this means $a,b$ would be residues. But the product of quadratic residues is another quadratic residue, which would mean $N=ab$ would need to be a quadratic residue. This is a contradiction, so $N$ is prime.