Dirichlet's 1842 Approximation theorem: Does this specific variant of the theorem actually exist?

207 Views Asked by At

From this pdf:

Theorem (Dirichle,1842)
Assume that $\gcd(a, b) = 1$. If $r,s$ are any natural numbers such that $\gcd(r,s) = 1$, and $|\frac{a}{b} − \frac{r}{s}| < \frac{1}{2s^2}$ then $\frac{r}{s}$ is one of the convergents of $\frac{a}{b}$.

I presume they mean Dirichlet. I'm trying to figure out the proof for Wiener' theorem on attacking the RSA cryptosystem and it would make my life a lot easier if this other theorem actually exists and is referable but I can't find this specific variant anywhere. Does it actually exist?

1

There are 1 best solutions below

0
On BEST ANSWER

This is Legendre's theorem in Diophantine approximations. See e.g. here. An extension, which also has applications on Wiener's type attacks on RSA and other similar cryptosystems can be found in this paper.