All Questions

It is well known extracting modular square roots modulo a composite number factors the modulus. On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...