Break RSA when modulus is of the form $N = pq$ with $|q^2 - p|$ small I need some insight in how to break the following RSA problem:


  From an RSA encryption scheme you know that the algorithm that
  generated the RSA modulus $N$ always outputs moduli of the form $N = pq$ such that the difference between $q^2$ and $p$ is not bigger than $2^8$
  in absolute value.


My question is: Shall I try to factor $N$? Which method should I use if so?

Somewhat related is this question. 

Edit: 
Solving for $q$, I have that $q$ is between the square root of $p-2^8$ and the square root of $p+2^8$.
You can find the factor $q$ just by taking the cube root of $N$ and rounding to the nearest integer!

If $N = pq$ where $p = q^2 + \delta$, then: $$\sqrt[3]N = \sqrt[3]{q(q^2 + \delta)} = \sqrt[3]{q^3 \left( 1+\frac{\delta}{q^2}\right)} = q \cdot \sqrt[3]{1+\frac{\delta}{q^2}}.$$

Thus, as long as $2|\delta| &lt; q$ then, given that $|1-x| \le |1-x^3|$ for all $x \ge 0$: $$\left|q - \sqrt[3]N\right| = q\left|1 - \sqrt[3]{1 + \tfrac{\delta}{q^2}}\right| \le q\left|1 - \left(1 + \tfrac{\delta}{q^2}\right)\right| = \tfrac{|\delta|}{q} &lt; \tfrac12,$$ and so $\sqrt[3]N$ rounds to $q$.

(A more precise calculation, using the fact that $q \ge 2$ and that $|1-\sqrt[3]{1+x}| \le \frac{|x|}2$ for all $|x| \le \frac12$, shows that this actually works even up to $|\delta| &lt; q$.)

More generally, even if $|\delta|$ could be several times as large as $q$, you could still solve the problem efficiently by starting with the approximate solution $\tilde q = \sqrt[3]N$ and testing nearby integers $q \approx \tilde q$ until you find one that evenly divides $N$.