Prime factorization of very large integer with quadratic residue and its square roots

Question

We have a very large modulus integer $n$ and we have very large number $y$. We know that $y$ is a quadratic residue modulo $n$. Also we know all $4$ square roots of $y$.

What is the best way of prime factorization of $n$ ?

Answer 1

If $a^2\equiv b^2\pmod N$, but $a\not\equiv b\pmod N$, then $g=\gcd(a-b,N)$ is a factor of $N$ with $1<g<N$.