# What is the computational complexity of Coppersmith's bivariate algorithm?

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?

• What is the running time? – Brout Nov 5 '18 at 10:22
• 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$ – kelalaka Nov 5 '18 at 10:25
• Elaborated the problem here. – Brout Nov 5 '18 at 10:26
• It does not say log N it says polynomial in log N. – Brout Nov 5 '18 at 10:27
• 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 – kelalaka Nov 5 '18 at 10:35