5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 1 is always a quadratic residue. $\endgroup$ – Yuval Filmus Dec 10 '15 at 7:08
5
$\begingroup$

You are completely right, and your algorithm is a randomized polynomial time algorithm for finding a quadratic non-residue modulo a prime. A major open question in algorithmic number theory is finding a quadratic non-residue deterministically in polynomial time. This is possible assuming the generalized Riemann hypothesis, but unknown unconditionally. It is also equivalent to extracting square roots modulo a prime. This is all explained in notes by Booher.

$\endgroup$
  • $\begingroup$ but it seems that the algorithm for finding Quadratic Residues and Non-residues is the same, just check -1 or +1 instead...is that right? $\endgroup$ – Charlie Parker Dec 10 '15 at 6:53
  • 1
    $\begingroup$ Finding a quadratic residue is easier, since 1 is always a quadratic residue. $\endgroup$ – Yuval Filmus Dec 10 '15 at 7:09
  • $\begingroup$ oh yea...duh of course 1 is always Quadratic Residue...I guess it only works for QR not equal to 1. $\endgroup$ – Charlie Parker Dec 10 '15 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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