# How does one find a non-quadratic residue modulo $p$?

I was wondering how one can find a non-quadratic residue modulo $p$ and what the runtime of this algorithm would be.

I thought that one can use the Legendre Symbol

$$\left( \frac{a}{p} \right) = a^{ \frac{(p-1)}{2} } \pmod p$$

if the Legendre Symbol returns -1 then its a non quadratic residue and if its a quadratic residue it would return 1. To do this it's easy find a randomized algorithm, since only half the elements are quadratic residues, then one guesses any element at random, say $a \in Z^*_p$ and if the Legendre Symbol returns -1 the return success. Since half the elements are not quadratic residues, it would take about 2 iterations in expectation to find one.

I was wondering, is this algorithm correct? It seems that its completely symmetrical for finding quadratic residues. I am not sure that is strange, but it seems weird to me. Is it correct that the two algorithms are basically the same?

• 1 is always a quadratic residue. – Yuval Filmus Dec 10 '15 at 7:08