# help understanding part of Wiener's attack on RSA w/ small d

In this paper, the author writes:

Now $k\phi(N) = ed - 1 < ed$. Since $e < \phi(N)$, we see that $k <d < \frac{1}{3}N^{\frac{1}{4}}$. Hence, we obtain:

$\mid \frac{e}{N} - \frac{k}{d} \mid \leq \frac{1}{dN^{\frac{1}{4}}} < \frac{1}{2d^2}$

I am having trouble seeing how these last equalities were found. I see how to get the following:
$\mid \frac{e}{N} - \frac{k}{d} \mid$ = $\frac{k}{d} - \frac{e}{N}$ $< \frac{3d}{dn^{\frac{1}{2}}}$

I do not see how to get from here to $\frac{1}{2d^2}$. Is anyone willing to explain this to me?

The previous part of the proof in that paper already shows that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{3k}{d\sqrt{N}}$. As $k < d$ we estimate this by $\frac{3d}{d\sqrt{N}}$, where the $d$'s cancel to get $\frac{3}{\sqrt{N}} = \frac{3}{N^{1 \over 2}} = \frac{3}{N^{1 \over 4}}\frac{3}{N^{1 \over 4}}\frac{1}{3}$.

As $d < \frac{1}{3}N^{\frac{1}{4}}$ we also get that $\frac{1}{d} > \frac{1}{\frac{1}{3}N^{{1 \over 4}}} = \frac{3}{N^{{1 \over 4}}}$.

Combining we get that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{1}{3d^2}$, which is even a better bound (the 2 might be the constant in the continued fraction convergents theorem, so that might explain it presence).

• Thanks, I wasn't seeing the inequality, but its very clean now Commented Dec 3, 2015 at 1:00