2
$\begingroup$

I'm struggling to understand the last part of Shor's algorithm, to be exact the point when we found $x-1$, $x+1$ with $x-1 ≠ 0\mod N$, $x+1 ≠ 0 \mod N$ and $(x+1)(x-1) = 0 \mod N$.

Then, $gcd(x-1, N) > 1$ and $gcd(x+1, N) > 1$ should hold true. Why is this the case? Is this so trivial to see? Especially the$\mod N$ confuses me here.

$\endgroup$

1 Answer 1

3
$\begingroup$

The assumptions $x\pm1\neq0\bmod N$ mean that neither of them is a multiple of (or equal to) $N$. That is, you cannot write $x+1=kN$ for some $k\in\mathbb{Z}$, and same for $x-1$.

At the same time, $(x+1)(x-1)=0\bmod N$ means that $(x+1)(x-1)=kN$ for some $k\in\mathbb{Z}$. This means all factors of $N$ are contained in this product. But by the previous assumption, they are not contained in $x+1$ or $x-1$ individually. So the only possibility is that some of the factors of $N$ are in $x+1$, and some of them are in $x-1$. This is equivalent to saying that the GCD between $x\pm1$ and $N$ is not one.

As an example, consider a simple case with $N=pq$ with $p,q$ coprimes. Then if $(x+1)(x-1)=kpq$ but $x\pm1\neq0\bmod pq$, then $x+1$ must contain $p$, and $x-1$ must contain $q$ (or vice versa). And that would mean $\operatorname{gcd}(x+1,N)=p>1$ and $\operatorname{gcd}(x+1,N)=q>1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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