Quantum Computers Can Find Quadratic Nonresidues in Deterministic Polynomial Time

Thomas G. Draper

An integer $a$ is a quadratic nonresidue for a prime $p$ if $x^2\equiv a\mathrm{mod}p$ has no solution. Quadratic nonresidues may be found by probabilistic methods in polynomial time.…