0

I am working on the following exercise:

I have to show that if for the two primes $p$ and $q$ used in RSA to compute $n$ holds:

$$p < q \le (1+\epsilon)*\sqrt{n}$$

one has to test at most $\frac{\epsilon^2\sqrt{n}}{2}$ values to find integers $s$ and $t$ such that $n = s^2-t^2$.

I do not know how I should start with this exercise, but I guess I need some algorithm that finds such a form for $n$. I think the straightforward idea would be to start at $\sqrt{n}$ and try out the numbers from there, but I guess I need a more systematic approach.

Unfortunately I am unable to find one. Could you help me?

Community
  • 1
3nondatur
  • 4,178
  • I edited the description, now it is complete. – 3nondatur May 29 '18 at 21:07
  • Although $\epsilon^2/2\sqrt n$ is correct it would be good to restructure it to make it clear the $\sqrt n$ is in the numerator, not the denominator. Stacked fractions, parentheses or reordering will all do the trick. – Ross Millikan May 29 '18 at 21:17

1 Answers1

2

You can just define $q=s+t, p=s-t$ and have $n=pq=s^2-t^2$.
We can invert the definitions to find $s=\frac12(p+q), t=\frac 12(q-p)$
Now if $$q \le (1+\epsilon)\sqrt n\\ p \ge \frac {\sqrt n}{1+\epsilon}\gt (1-\epsilon+\epsilon^2)\sqrt n\\s \lt \sqrt{n}+\frac {\epsilon^2}2\sqrt n $$

Quotenbanane
  • 1,594
Ross Millikan
  • 374,822
  • Sorry, but I don't get the line $\frac{\sqrt{n}}{1+\epsilon} \gt (1-\epsilon+\epsilon^2)\sqrt{n}$, could you elaborate that? – 3nondatur May 29 '18 at 21:40
  • It is just the expansion of $\frac 1{1+x}$ as $1-x+x^2-x^3+\ldots$ terminated after the square term. This converges when $|x|\lt 1$ The alternating series theorem says the error is the sign of and smaller than the first neglected term, justifying the $\gt$ sign – Ross Millikan May 29 '18 at 21:43
  • I see, thanks a lot for your help. – 3nondatur May 29 '18 at 21:43