Breaking RSA with Factor in Range of $\sqrt{N}$ Suppose on of the RSA prime factors $p$ is the range of $\sqrt{N}$, in particular it holds that $|p-\sqrt{N}|&lt;\sqrt[4]{N}$
I want to show that RSA can be broken in time poly(log N)
Given hint: $N = pq = (\frac{p+q}2)^2 - (\frac{p-q}2)^2 $ , also $\frac{p+q}2 \approx \sqrt{N}$
$\textbf{This is my approach:}$
First of all, we can calculate $\sqrt{N}$
From $|p-\sqrt{N}|&lt;\sqrt[4]{N}$ we know that $p$ can only be $2 \sqrt[4]{N}$ distinct values, namely anything in$ \{\sqrt{N}- \sqrt[4]{N}, ...,\sqrt{N} + \sqrt[4]{N} \}$
Of course $\sqrt{N}$ is usually not a whole number, but we can round up
So now we can test for every element $p$ in this set, if $p | N$ , in which case we could easily calculate the other factor
If i am not mistaken, this reduced bruteforce would cost $\mathcal{O} ( \sqrt{N} )$ , which does not seem to match with what we want to show, e.g. $\mathcal{O} ( \sqrt{N} )$ $\not=$ poly(log N)
Although this might not be the solution you're looking for, the Coppersmith theorem offers a simple answer to this.
The (general) Coppersmith theorem states: let $f(x)$ be a monic univariate polynomial of degree $d$ with coefficients modulo a positive integer $n$. One can find all integers $x$ such that $|x| \le n^{\beta^2/d}$ and $\gcd(f(x), n) \ge n^{\beta}$ (or $f(x) = 0 \bmod b$, $b$ an unknown divisor of $n$ of size $\ge n^{\beta}$) in time polynomial in $\log n$ and $d$.
Now here we have $|p - \sqrt{n}| &lt; n^{1/4}$. Setting $f(x) = x - \lfloor \sqrt{n} \rfloor$, this means that there is an $x_0$  bounded in absolute value by $n^{\left(1/2\right)^2} = n^{1/4}$ such that $\gcd(x_0 - \lfloor \sqrt{n} \rfloor, n) \ge n^{1/2}$ (that is, a factor of $n$), and such an $x_0$ can be found in polynomial time in $\log n$.