0
$\begingroup$

The Wikipedia article on Shor's algorithm says:

The aim of the algorithm is to find a square root $b$ that is different from $1$ and $-1$; such a $b$ will lead to the factorization of $N$, as in other factoring algorithms like the quadratic sieve.

I'm not quite sure how finding such a $b$ will lead to the factorization of $N$. Nevertheless, I will write down what I understood so far.

Say we find a $b$ (apart from $1$ and $-1$) such that

$$b^2 \equiv 1 \pmod N$$

$$\implies b^2-1^2 \equiv 0\pmod N$$

$$\implies (b-1)(b+1) \equiv 0 \pmod N.$$

Then computing the GCD of $b-1$ or $b+1$ with $N$ will produce a factor of $N$, although it might be a trivial factor ($1$ or $N$). If it's a trivial factor we should try with a different $b$, as there are at least two possible values of $b$, apart from $1$ and $-1$, as a consequence of the Chinese Remainder Theorem.

Is this the correct way to find a factor of $N$ (as stated on the Wiki article) or am I missing something?

Note: $N$ is an odd composite number.

$\endgroup$
3
  • 1
    $\begingroup$ If $b\ne \pm 1\mod N$, you actually get a non-trivial factor this way. $\endgroup$
    – Peter
    Commented Feb 16, 2019 at 13:59
  • $\begingroup$ @Peter Interesting! If possible, could you elaborate on "why" in an answer below? $\endgroup$
    – user568976
    Commented Feb 16, 2019 at 14:00
  • 2
    $\begingroup$ $\gcd(b\pm 1,N)$ cannot be $N$ because that would imply $N\mid b\pm1$, i.e., $b\equiv \mp 1\pmod N$. And $\gcd(b\pm1,N)$ cannot be $1$ because that would imply $N\mid b\mp1$, so $b\equiv\pm1\pmod N$. $\endgroup$ Commented Feb 16, 2019 at 14:02

1 Answer 1

0
$\begingroup$

Well, in general for factor basis algorithms for factorization, if you finally obtain $b^2\equiv c^2\mod n$ and $b\not\equiv \pm c\mod n$, then compute $\gcd(b+c,n)$, which will be a nontrivial factor of $n$.

$\endgroup$
2
  • $\begingroup$ Thanks. But why is the $b\not\equiv \pm c\pmod n$ condition necessary here? $\endgroup$
    – user568976
    Commented Feb 16, 2019 at 14:12
  • $\begingroup$ It would be a trivial relation. $\endgroup$
    – Wuestenfux
    Commented Feb 16, 2019 at 14:19

You must log in to answer this question.