# How do I find solutions of a quadratic Diophantine equation mod a large composite?

I'd like to find integral solutions to the equation

$2x^2 -3xy + y^2 \equiv 0 \mod n$

where $n$ is a given composite, for example, $n = 16807708473783470801$ (I prefer solutions that work for any $n$). I don't know the factorization of $n$, though I do know it is a product of two large, distinct primes.

Any thoughts? I know being able to quickly find solutions to $x^2 \equiv y^2 \mod n$ is equivalent to factoring, so I'm not super hopeful for provably fast algorithms for my problem - I'd be happy for heuristics, links to Mathematica documentation, etc.

Would the problem become any easier or richer if I replaced the quadratic with a cubic? In that case I'd expect techniques from the theory ellipic curves to play a role..

• Completing the square shows that it is equivalent to solving $x^2 \equiv y^2 \bmod n$ and thus to factoring $n$. – Franz Lemmermeyer Aug 7 '17 at 6:03

Denote $n=pq$ for primes $p,q$. Your equation is equivalent to $(y-x)(y-2x)\equiv 0\pmod n$. If you find a solution for which neither $y-x$ nor $y-2x$ is divisible by $n$, then the greatest common divisor of $y-x$ and $n$ equals either $p$ or $q$. So, you quickly factor $n$, that is hard.