Solving bivariate quadratic congruences in random polynomial time

It has been known for some time that solving ${x^2} \equiv a\;(\bmod n)$ is as difficult as factoring n, at least in the sense that the two problems are random polynomial time equivalent. By contrast, solving a bivariate quadratic congruence ${x^2} - k{y^2} \equiv m\;(\bmod n)$ can usually be done in random polynomial time even if the factorization of n is unknown. This was first proved by Pollard and Schnorr in 1985 under the assumption of the Piltz conjecture for Dirichlet L-functions. We now prove the result without assuming any unproved hypothesis.