An integer $a$ is a quadratic residue with respect to prime $p$ if $a \equiv x^2 \mod{p}$ for some integer $x$.
Given a prime $p$ and an integer $a$, how fast can we decide whether $a$ is a quadratic residue modulo $p$? As it turns out (courtesy to Euler), pretty fast.