Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 5 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|improve this answer

Your Answer

 
discard

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.