# 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)$"

• Hint: you know that $y^2\equiv 1 \pmod n$ and you know that $y\not\equiv 1 \pmod n\Leftrightarrow (y-1)(y+1)\equiv 0 \pmod n\Leftrightarrow (y-1)(y+1)=k\cdot n$ – SEJPM Jun 30 '16 at 11:19

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.
• "$y \not \equiv \pm 1 \pmod n$ means that neither $y+1$ and $y-1$ is a multiple of n" is because: $\\$ for $y=+1$ we'd have $y-1= 0\pmod n \Rightarrow \ y-1$ multiple of $n$ and for $y=-1$ we'd have $y+1= 0\pmod n \Rightarrow \ y+1$ multiple of $n$ , right? – Alessio Martorana Jun 30 '16 at 11:57
• Could you please explain me the reasoning why if $gcd(y-1,n) = 1 \Rightarrow$ $n$ divides $(y+1)$ ? – Alessio Martorana Jun 30 '16 at 12:17