Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) [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$


1 Answer 1


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}. $$


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.