Breaking RSA with Factor in Range of $\sqrt{N}$

Question

Suppose on of the RSA prime factors $p$ is the range of $\sqrt{N}$, in particular it holds that $|p-\sqrt{N}|<\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}|<\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)

Answer 1

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}| < 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$.

Answer 2

TL;DR This is exactly what is needed for the Fermat factoring method to succeed fast.

It is easy to show that $q$ is also within a range of $\sqrt[4]{N}$ of $\sqrt{N}$ up to a little discrepancy.

Then, we can approximate $p+q$ as $2\sqrt{N}$:

$(p+q) - 2\sqrt{N} = \sqrt{(p+q)^2} - 2\sqrt{N} = \sqrt{(p-q)^2 + 4N} - 2\sqrt{N} = 2\sqrt{N}(\sqrt{(q-p)^2/4N+1}-1)$

Using $0 \le q-p\le 2\sqrt[4]{N}$ and $\sqrt{1+x}-1 = x/2 + O(x^2)$,

$0 \le (p+q) - 2\sqrt{N} \le 2\sqrt{N}(\sqrt{1/\sqrt{N}+1}-1) = 2\sqrt{N}( 1/2\sqrt{N} + O(1/N) = 1 + O(1/\sqrt{N}).$

We see that the approximation is valid up to a small constant. Thus, the Fermat method succeeds immediately or we can also use a few candidate for $p+q$ to factor $N=pq$.