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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.