justification for method to factorize n knowing RSA private exponent d I know that knowing the private exponent $d$ corresponding to the private key $k_{pub}\langle n,e\rangle$ it is possible to efficiently factorize n.

The procedure starts stating that:

$ed -1 = s(p-1)(q-1)$

and then saying that:

Randomly picking $x\in\mathbb{Z}_n^*$ we know that $x^{ed-1}\equiv 1\pmod n$ and computing $y=\sqrt{x^{ed-1}}=x^{\frac{ed-1}2}$

We have the identity:

$y^2-1$

And so:


If $y\neq\pm1\pmod n$, a factor of $n$ is obtained as: $gcd(y-1,n)$
If $y=-1\pmod n$, we repeat this procedure from the beginning and pick
another value for $x$
If $y=+1\pmod n$, we iterate the whole procedure starting from the square root of $y^2$


Could someone give me a justification for this? Especially for:

"If $y\neq\pm1\pmod n$, a factor of $n$ is obtained as: $gcd(y-1,n)$"
We have $y^2-1 \equiv 0 \pmod n$, meaning that $y^2-1 = (y+1)(y-1)$ is a multiple of $n$. $y \not \equiv \pm 1 \pmod n$ means that neither of $y+1$ and $y-1$ is a multiple of $n$. Now, clearly $\gcd(y-1,n)$ is a divisor of $n$; we want to show that it is not $1$ or $n$.


It cannot be $1$, because that would imply that $n$ divides $y+1$, which we assume is not the case.
Likewise it cannot be $n$, because that would imply that $n$ divides $y-1$.


The reason we take $y$ such that $y^2 - 1 \equiv 0 \pmod n$, by the way, is so that we have a good chance of finding a non-trivial factor. Indeed, if we just pick any random $y$, it is overwhelmingly likely that $\gcd(y-1,n) = 1$, which does not help us.