# 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 :)

• Hint to show: $\frac{p+q}2\geq\sqrt N$: Start from $0\leq (x-y)^2$ (or find the the right Wikipedia article ;)
– SEJPM
May 14 '17 at 13:08
• Thanks, it helped indeed. I was not aware of the "Inequality of arithmetic and geometric means". May 14 '17 at 15:34

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.

• Also see Inequality of arithmetic and geometric means on Wikipedia and note how $N=pq$.
– SEJPM
May 14 '17 at 14:33
• Thanks :) I edited my post to add the solution. I will try to figure out the last step. I hope I am able to find a way. Will let you keep updated. May 14 '17 at 15:43
• I tried to find a way to get the algorithm in order to retrieve $p$ and $q$ in time $\tilde{O}(1)$ but I have no clue on how to go on :( May 14 '17 at 19:59
• @Donut: try the strategy of searching $p+q\over2$ by testing integer values $s$ starting from $\left\lceil\sqrt N\,\right\rceil$, going onwards, until $s^2-N$ happens to be a square, in which case that is $\left(p-q\over2\right)^2$.Show that factorization follows, find how many steps are required, and how to make the cost $O(\sqrt[4]N)$
– fgrieu
May 14 '17 at 20:13
• Ok, here is how I would do it based on your hint. I know that $p-q=2\sqrt{2}\sqrt[4]{N}$ is. With a bit of math I could form it to $(\frac{p-q}{2})^2 = 2*\sqrt{N}$. This would be something I am able to calculate. Then I test integer values $s$ starting from $\lceil \sqrt{N}\rceil$. For each $s$ I check if $s^2 - N = (\frac{p-q}{2})^2$. If it is, I have $s = \frac{p+q}{2}$ and $\sqrt{s^2 - N} = \frac{p-q}{2}$. With these I am able to factorize $N$: $\frac{p+q}{2} - \frac{p-q}{2}=\frac{p+q-(p-q)}{2} = \frac{2q}{2}=q$. Are these steps correct so far? May 14 '17 at 21:14