Let's say we have $n=pq$ with $p,q$ prime. We can write $n=s^2-t^2$ for some whole numbers $s,t$.
Now prove that if $q<p\leq (1+\epsilon)\sqrt{n}$ then $s$ has at most $\frac{\epsilon^2}{2}\sqrt{n}$ values, i.e. the number of values we need to test to find $n=s^2-t^2$.
My attempt:
I figured, that $n=s^2-t^2 = (s+t)(s-t) = pq$, therefore $p=s+t$ and $q=s-t$ assuming $s,t\geq 0$
So $s+t \leq (1+\epsilon)\sqrt{n}$ and $ s-t \leq (1+\epsilon)\sqrt{n}$ which means $s \leq (1+\epsilon)\sqrt{n}$
But what then? Am I even on the right track?