3
$\begingroup$

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

$\endgroup$
  • 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 '17 at 13:08
  • $\begingroup$ Thanks, it helped indeed. I was not aware of the "Inequality of arithmetic and geometric means". $\endgroup$ – Donut May 14 '17 at 15:34
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Also see Inequality of arithmetic and geometric means on Wikipedia and note how $N=pq$. $\endgroup$ – SEJPM May 14 '17 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 '17 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 '17 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 '17 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 '17 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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