Proving Wiener's attack on RSA: help understanding what is meant by a "classic approximation relation"?

Question

I am researching Wiener's attack on the RSA cryptosystem. The theorem, found here beginning on page 4, is as follows:

Let $N=pq$ with $q < p < 2q$. Let $d < \frac{1}{3}N^\frac{1}{4}$. Given $(e, N)$ with $ed = 1\bmod\varphi({N})$, a malicious attacker can efficiently recover $d$.

I am stuck near the very end of the proof:

$\left|\frac{e}{N} - \frac{k}{d}\right| \leq \frac{1}{d\sqrt[4]{N}} < \frac{1}{2d^2}$.

This is followed by the statement "This is a classic approximation relation. The number of fractions $\frac{k}{d}$ with $d<N$ approximating $\frac{e}{N}$ so closely is bounded by $log_2 N$."

I don't understand what is meant by classic approximation relation, nor where the bound $log_2 N$, comes from. Could anyone help?

Answer 1

By Legendre's theorem in Diophantine approximations, if $|\alpha - \frac{k}{d}|< \frac{1}{2d^2}$, then $k/d$ has to be a convergent $p_m/q_m$ of continued fraction expansion of $\alpha$. Since the denominators $q_m$ grow exponentially ($q_m \geq F_m$, where $F_m$ is $m$-th Fibonacci number), there are less then $\log_2 N$ convergents (i.e. candidates for $k/d$) with $k<N$.

Answer 2

I may be missing some important observation, and I don't know what is meant by classic approximation relation and where the bound comes from, either , but maybe the following helps, nonetheless: (assuming $d, k$ are integers, $q$ is a fixed rational number and $d\ge2$) if you have a relation $$|q-\frac{k}{d}|< \frac{1}{2d^2}$$ then there is at most one number $k$ for which such a relation can hold (you are looking at a number of the form $\frac{k}{d}$ in the interval $(q-\frac{1}{2d^2},q+\frac{1}{2d^2})$ of width $\frac{1}{d^2} < \frac{1}{d}$).