Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.