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?
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 $$