1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – SEJPM Jun 30 '16 at 11:19
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "$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? $\endgroup$ – Alessio Martorana Jun 30 '16 at 11:57
  • $\begingroup$ This seems obvious. $\endgroup$ – fkraiem Jun 30 '16 at 11:58
  • $\begingroup$ Just wanted to be sure =) $\endgroup$ – Alessio Martorana Jun 30 '16 at 11:59
  • $\begingroup$ Could you please explain me the reasoning why if $gcd(y-1,n) = 1 \Rightarrow$ $n$ divides $(y+1)$ ? $\endgroup$ – Alessio Martorana Jun 30 '16 at 12:17
  • $\begingroup$ @AlessioMartorana Euclid's Lemma. $\endgroup$ – fkraiem Jun 30 '16 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.