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

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

1 Answer 1


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.

  • 2
    $\begingroup$ Also see Inequality of arithmetic and geometric means on Wikipedia and note how $N=pq$. $\endgroup$
    – SEJPM
    May 14, 2017 at 14:33
  • $\begingroup$ 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. $\endgroup$
    – Donut
    May 14, 2017 at 15:43
  • $\begingroup$ 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 :( $\endgroup$
    – Donut
    May 14, 2017 at 19:59
  • $\begingroup$ @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)$ $\endgroup$
    – fgrieu
    May 14, 2017 at 20:13
  • $\begingroup$ 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? $\endgroup$
    – Donut
    May 14, 2017 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.