While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$. If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$. However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 3/4 of the possible $m$ values will result in a factorization, hence this method is practical.

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$. If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$. However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 1/2 of the possible $m$ values will result in a factorization, hence this method is practical.

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$. If it is 1 9r $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$. However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 3/4 of the possible $m$ values will result in a factorization, hence this method is practical.

While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$. If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$. However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 3/4 of the possible $m$ values will result in a factorization, hence this method is practical.