http://www.numbertheory.org/pdfs/general_quadratic_solution.pdf gives a general method to solve quadratic bivariate diophantine equation while Coppersmith introduced a method to solve bivariate polynomials which work provably and have been shown to break $RSA$ system if half of low significant bits of either $P$ or $Q$ are known.

The equation that comes out is $$(2^ku+v)(2^ku'+v')=PQ$$ where if we assume $v$ is known. Then $vv'\equiv PQ\bmod 2^k$ gives $v'$.

So we have a quadratic diophantine equation $$2^kuu'+(uv'+u'v)=\frac{PQ-vv'}{2^k}.$$

Why do I need Coppersmith's method to solve this? Can't a regular diophantine solver work here and so are there explicit polynomials where Coppersmith is better than standard solver in bivariate quadratic case?


Partial answer about "regular diophantine solver".

Finding points on conics in general require integer factorization.

Several papers deal with points on $a x^2+b y^2=c z^2$ and they require factorization of $a,b,c$.

Another example is $x^2 - a y^2=n z^2$. Solving it will compute the square root of $a$ modulo $n$.

Coppersmith method avoid factorization at the cost of small solutions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.