RSA: Proving that $p+q-1 < 3 \sqrt{N}$, where N = pq and p,q are prime? I'm doing some research into attacks on the RSA cryptosystem and have stumbled across Wiener's attack. Within the proof there exists the statement  "$p+q-1 &lt; 3\sqrt{N}$".
No proof is given for this, and I can't seem to figure out why this statement holds. Could anyone help me figure this out or point me towards the relevant theorems?
There is likely an assumption on the sizes of $p$ and $q$ that you haven't listed in your question that exists in the description. For example, Boneh's description of Wiener's attack has that $q&lt;p&lt;2q$.

With that assumption, we can prove the inequality.

We know that

$$p+q &lt; 2q+q$$
$$p+q &lt; 3q$$

Furthermore, since $N=pq$ and $p&gt;q$, we have that $\sqrt{N} &gt; q$, or $3\sqrt{N} &gt; 3q$. So

$$p+q &lt; 3q &lt; 3\sqrt{N}$$

In your inequality, you have $p+q-1$ which is clearly smaller than $p+q$, so everything works out, $p+q-1 &lt; 3\sqrt{N}$.