6

From Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) (arXiv), p. 15:

To find a factor of an odd number $n$, given a method for computing the order $r$ of $x$, choose a random $x \pmod n$, find its order, and compute $\text{gcd}(x^{\frac{r}{2}}-1,n)$. Here $\text{gcd}(a,b)$ is the greatest common divisor of $a$ and $b$, i.e., the largest integer that divides both $a$ and $b$. The Euclidean algorithm [Knuth 1981] can be used to compute $\text{gcd}(a,b)$ in polynomial time. Since $$(x^{\frac{r}{2}}+1)(x^{\frac{r}{2}}-1) \equiv 0 \pmod n,$$ then $\text{gcd}(x^{\frac{r}{2}}-1, n)$ fails to be a non-trivial divisor of $n$ only if $r$ is odd or if $x^{\frac{r}{2}} \equiv -1 \pmod n$. Using this criterion, it can be shown that this procedure, when applied to a random $x \pmod n$, yeilds a factor of $n$ with probability $1-2^{k-1}$, where $k$ is the number of distinct odd prime factors of $n$. A brief sketch of the proof of this result follows. Suppose that $n = \prod_{i=1}^{k} p_i^{a_i}$. Let $r_i$ be the order of $x \pmod {p_i^{a_i}}$. Then $r$ is the least common multiple of all $r_i$. Consider the largest power of $2$ dividing each $r_i$. The algorithm only fails if all these powers of $2$ agree: if they are all $1$, then $r$ is $1$, then $r$ is odd and $\frac{r}{2}$ does not exist; if they are all equal and larger than $1$, then $x^{\frac{r}{2}} \equiv -1 \pmod n$ since $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ for every $i$.

I know that in factoring algorithms the general idea is that if we can obtain $b^2\equiv c^2 \pmod n$ and $b\not\equiv \pm c\pmod n$, then $\gcd(b+c,n)$ will be a non-trivial factor of $n$. So far so good.

But then it is not clear to me why $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ for every $i$, in this context. It doesn't seem to logically follow from "all these powers of $2$ (i.e. the highest powers of $2$ that divide each $r_i$) agree" and "if they are all equal and larger than $1$".

I'm probably missing something. Could someone clarify?

Related: Shor's algorithm caveats when $a^{r/2} =-1 \mod N$

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49
Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112

1 Answers1

3

If $r$ is the least common multiple of the $r_i$, then for each $r_i$ there is an integer $s_i$ such that $r=r_is_i$. If at least one of the $r_i$ is even, then so is $r$, which we need.

Moreover, if all the $r_i$ agree on the powers of 2 dividing the $r_i$, then $r$ contains the same number of powers of 2, and $s_i$ must be odd. Hence, for each $i$, $$ x^{r/2}\text{ mod }p_i^{a_i}=(x^{r_i/2})^{s_i}\text{ mod }p_i^{a_i} $$ Now, we know that $$ x^{r_i}-1=(x^{r_i/2}+1)(x^{r_i/2}-1)\equiv 0\text{ mod }p_i^{a_i} $$ but $x^{r_i/2}-1$ is not 0 modulo $p_i^{a_i}$ because otherwise the order would be $r_i/2$, not $r_i$. So, $$ x^{r/2}\text{ mod }p_i^{a_i}=(-1)^{s_i}\text{ mod }p_i^{a_i}=(-1)\text{ mod }p_i^{a_i}. $$

DaftWullie
  • 62,671
  • 4
  • 55
  • 140