Coppersmith's original paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known says the algorithm to find bivariate roots under certain conditions runs in polynomial time on certain parameters.

What is this complexity to find roots?

  • $\begingroup$ What is the running time? $\endgroup$ – Brout Nov 5 '18 at 10:22
  • 1
    $\begingroup$ The corollary 2 says that; If we know ab integer $N= P Q $ and we know the higher order $(1/4)(\log_2 N)$ bits of $p$, then in time polynomial $\log N$ we can discover $P$ and $Q$ $\endgroup$ – kelalaka Nov 5 '18 at 10:25
  • $\begingroup$ Elaborated the problem here. $\endgroup$ – Brout Nov 5 '18 at 10:26
  • $\begingroup$ It does not say log N it says polynomial in log N. $\endgroup$ – Brout Nov 5 '18 at 10:27
  • 1
    $\begingroup$ A polylogarithmic function in $N$ is a polynomial in the logarithm of $N$, $a_k(\log N)^k+\cdots+a_1(\log N)+a_0$, from wiki $\endgroup$ – kelalaka Nov 5 '18 at 10:35

Your Answer

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

Browse other questions tagged or ask your own question.