Return to Question

Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

It suffices to show that $|e/n-k/d| > 1/d^2$.

Thank you!

Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

It suffices to show that $|e/n-k/d| > 1/d^2$.

Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

It suffices to show that $|e/n-k/d| > 1/d^2$.