4th Root of RSA Modulus Attack algorithm I am trying to solve here a task but I have no clue on how to approach it. The last few days I tried to find a way but I have no clue :( Maybe someone of you could give me a hint on how to do it.

The following assumption is given: $p-q=O(\sqrt[4]{N})$

Using the given assumption I have to show that it is possible to retrieve $p$ and $q$ in time $\tilde{O}(1)=poly(logN)*1$.

The following hint is given: $N=pq=(\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$, whereby I should first show that $\frac{p+q}{2}\ge\sqrt{N}$. For the proof I can assume that $p-q=2\sqrt{2}\sqrt[4]{N}$.

I am clueless. I tried first to show $\frac{p+q}{2}\ge\sqrt{N}$ but I am wondering on how to get the $\ge$. I tried to solve the hint with by replacing $p-q$ with $2\sqrt{2}\sqrt[4]{N}$ and try to get a solution. All I get is:

$N=pq=(\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$

$N=pq=(\frac{p+q}{2})^2 - (\frac{2\sqrt{2}\sqrt[4]{N}}{2})^2$

$N=pq=(\frac{p+q}{2})^2 - 2\sqrt{N}$

I don't see how this could help me. 
Thank you for every hint.



Thanks guys for the hints. Here is the first prove:

$0 \ge -(\frac{p-q}{2})^2$

$(\frac{p+q}{2})^2 \ge (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$

$ (\frac{p+q}{2})^2 \ge N$

$ \frac{p+q}{2} \ge \sqrt{N}$

It hope it's all correct and I did not mistype sth. I will see if I am able to figure out the next step :)
It hold that $0\ge-\left({p-q\over2}\right)^2$. We add $\left({p+q\over2}\right)^2$ on both sides and use $N=\left({p+q\over2}\right)^2-\left({p-q\over2}\right)^2$ (hinted, and easily established from $N=p\,q$ ). We get $\left({p+q\over2}\right)^2\ge N$. From that, by taking the square root of both sides (which we can do since the quantities are non-negative), we get $\frac{p+q}{2}\ge\sqrt{N}$, QED.



The fun part is after this warmup..

The general idea is to search for $s={p+q\over2}$, by searching integers $s$ incrementally starting from $s_0=\left\lceil\,\sqrt N\,\right\rceil$, until $s^2-N$ is the square of some integer $t$; that is $\exists t\in\mathbb N$ with $t^2=s^2-N$, or equivalently $\sqrt{s^2-N}$ is an integer.

Notice that ${p+q\over2}$ is an integer when $N$ is an odd composite, and we just proved ${p+q\over2}\ge\sqrt N$, thus ${p+q\over2}\ge s_0$, thus the above strategy insures $s$ will ultimately reach $p+q\over2$. When that happens, we'll have $t={p-q\over2}$, and we'll thus be able to get $p=s+t$ and $q=s-t$, leading to a factorization of $N$ (perhaps partial if $N$ has more than two factors).

Speed depends on:


How many $s$ there are to test, that is how high $s$ will get over $s_0$. With a little algebra, an upper bound can be found by assuming $p-q\le2\sqrt{2}\sqrt[4]{N}$, which is how I read one of the hints; or it can be directly found an asymptotic bound using the assumption $p-q=O(\sqrt[4]{N})$.
How fast we can determine that $s^2-N$ is not a square (or better, summarily skip a sizable fraction of candidates for $s$); for example, in base $10$, squares never have their rightmost digits among $\{2,3,7,8\}$ and that helps get rid of some $s$ without computing a square root. However, such tweaks (many are possible) are not necessary to get the desired asymptotic bound, with polynomial of unspecified order.


This is known as the Fermat factorization algorithm.