I'm trying to prove:
$$(a+b)^2 \leq 9ab$$ and don't know how to proceed from the conclusion in the title.
Note that $a$ and $b$ have to be large primes.
In the last line of page 11 of the following paper:
What I'm trying to prove above is used. I'm not sure how the equivalence holds.
$\endgroup$ 83 Answers
$\begingroup$Consider $b=2$ and $a=3571$, the $500^{\text{th}}$ prime, to see that this is clearly false.
$\endgroup$ 25 $\begingroup$If $b\gt7a\gt0$, then $a^2+b^2-7ab=a^2+b(b-7a)\gt0$, so counterexamples such as $(a,b)=(2,17)$ are easy to find.
Note, thought, that if we require $a$ and $b$ to have the same number of bits, so that $a\lt b\lt 2a$, then
$$(a+b)^2\lt(a+2a)^2=9a^2\lt9ab$$
This might explain the inequality in the linked-to paper.
$\endgroup$ 5 $\begingroup$The line you are referring to reads $|\hat d-d|\le k(p+q)/e\le 3k\sqrt N/e<3\sqrt N $. I suppose you wonder how one can arrive at the "$\le$" in the middle. Indeed, that inequality is equivalent to $(p+q)^2\le 9pq$. With $\alpha:=\frac qp$, the inequality $(p+q)^2\le 9pq$ is equivalent to $(1+\alpha)^2\le 9\alpha$, or approximately $0.146<\alpha < 6.85$, so this is just a consequence of what is said in the introduction: that $p$ and $q$ are "large primes of the same size". Incidentally, a good implementation of RSA might well decide to make $\frac qp$ larger than that (and avoid many other pitfalls, such as $\alpha$ having a simple continued fraction)
$\endgroup$
