# 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}|<\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)

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

• Do you know who published this nice technique? It seems way better (or less hopeless, rather) in practice than Fermat factoring. And it makes the prescription $\lvert p–q\rvert>2^{(n_\text{len}/2)–100}$ of FIPS 186-4, section B.3.1, item 2(d) look even stranger. Of course, probability that $|p-\sqrt n|<\sqrt[4]n$ is so low [ $\lesssim14/2^{(n_\text{len}/4)}$ with the prescribed ranges for $p$ and $q$ I believe] that, even combined with Lehman's enhancement, it's still not a factorization technique applicable to RSA moduli. – fgrieu May 10 at 8:46
• Well, knowing that $|p - \sqrt{n}| \le n^{1/4}$ is really the same as saying that you know half of the most significant bits of a factor. So Coppersmith already did this back in 1996. However his method was more complicated and used a bivariate polynomial. Boneh and Howgrave-Graham first came up with the theorem as above. May popularized it in his PhD thesis. – Samuel Neves May 10 at 19:04

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