Does being able to factor semiprimes entail being able to factor any number?

Question

I'm asking this question with specific reference to Shor's Quantum Factorization Algorithm, which uses the fact that finding a non-trivial square root of $1 \pmod N$ for some integer $N$ yields factors of $N$. The plausibility of this setup (i.e. the fact that we don't have to hope to be overly lucky for this to work) relies on the following claims:

1. Let $x$ be chosen randomly from $0 \leq x < p$ is prime. We know that there exists a generator of $\mathbb{Z}_p$, call it $g$, so that $g^k \pmod p = x$. If $k$ is odd, then $\text{ord}(x)$, defined to be the minimum $r$ such that $x^r \pmod p = 1 \pmod p$, is even. Consequently, the probability that $\text{ord}(x)$ is even for a random $x$ is at least $1/2$.

2. If $N = pq$ for primes $p$ and $q$, then with probability at least $3/8$ the order $r$ of a randomly chosen element $x \in \mathbb{Z}_{pq}$ is even, and furthermore, $x^{r/2} \pmod {pq} \neq \pm 1 \pmod {pq}$. The proof of this is roughly as follows:

Choosing a random $x$ in $\mathbb{Z}_{pq}$ is equivalent to choosing some $a \in \mathbb{Z}_p$ and $b \in \mathbb{Z}_q$. Namely, given some $a = x \pmod p$ and $b \pmod q$, there is exactly one element in $\mathbb{Z}_{pq}$ satisfying these relations, by the Chinese Remainder Theorem. Letting $r_a = \text{ord}(a)$ (with respect to $\mathbb{Z}_p$) and $r_b = \text{ord}(b)$ (with respect to $\mathbb{Z}_q$), clearly we can see that $r_a, r_b ~|~ r$ (where $r = \text{ord}(x)$ with respect to $\mathbb{Z}_{pq}$). From result one, $r_a$ and $r_b$ are even with probability at least $1/2$, so $r$ will be even with probability at least $3/4$.

In addition, we claim that if $r$ is even, the probability that $x^{r/2} \pmod {pq} = \pm 1$ is at most $1/2$. Since $x^{r} = 1 \pmod {pq}$ if and only if $x^r = 1 \pmod p$ and $x^r = 1 \pmod q$, and these in turn imply that $x^{r/2} = \pm 1 \pmod p$ and $x^{r/2} = \pm 1 \pmod q$. We can form four systems of two equations with these, and they will each have unique solutions $x \in \mathbb{Z}_{pq}$. Two of them are $\pm 1$, and thus the other two will thus be non-trivial. The result then follows.

What I fail to see is how this can extend to factoring numbers in general. What if the number were of the form $p^2 q^3$, or $pqr$ (where $p, q, r$ are prime)? Is it either possible to tweak one of these results and its proof so that we can find a non-trivial square root for any $N$ (not just those which are semiprime)? Or alternatively, is there some simple explanation for why factoring just reduces to factoring a semiprime? Thanks!

UPDATE: It appears that the following is true (Theorem 5.3 in Nielsen and Chuang, Quantum Computation and Quantum Information):

Suppose $N$ is odd and has $m$ distinct prime factors. If we choose $x$ uniformly under the constraint $\gcd(x, N) = 1$ and $r$ is the order of $x$ modulo $N$, then $$\mathbb{P}(r \text{ is even and } x^{r/2} \neq -1 \pmod N) \geq 1 - 2^{-m}$$

But no proof or proof reference is given. If someone can prove this assertion, that would answer my question as well.

Answer 1

I've found the proof of this statement in Nielsen and Chuang, Quantum Information and Quantum Computing, Appendix 4 (thanks to @DaftWullie on QC Stack Exchange). The claim which I believe is correct is slightly different:

Suppose $N$ is odd and has $m$ distinct prime factors. If we choose $x$ uniformly under the constraint $\gcd(x, N) = 1$ and $r$ is the order of $x$ modulo $N$, then $$\mathbb{P}(r \text{ is even and } x^{r/2} \neq -1 \pmod N) \geq 1 - 2^{1-m}$$

Let $\mathbb{Z}_{N}^*$ be the multiplicative group of integers less than $k$ that are relatively prime to $k$. The proof of the statement relies on the following lemma:

Let $p$ be an odd prime. If $2^d$ is the largest power dividing $\varphi(p^a) = p^{a-1}(p-1)$, then with probability $1/2$ a randomly chosen element of $\mathbb{Z}_{p^a}^*$ will have order divisible by $2^d$.

Proof: $\mathbb{Z}_{p^a}^*$ is cyclic, so there exists a generator $g$ for it, i.e. every element is expressible as $g^k \pmod {p^a}$ for some $k < \varphi(p^a)$. Suppose $x = g^k \pmod {p^a}$ and the order of $x$ modulo $p^a$ is $r$. Consider two cases. If $r$ is odd, then $g^{kr} \pmod {p^a} = 1$, so $\varphi(p^a)$ divides $kr$ (since the order of $g$ must be $\varphi(p^a)$). Since $k$ is odd, $2^d ~|~ r$. Now if $k$ is even, then $$x^{\varphi(p^a) /2} \pmod {p^a} = g^{\varphi(p^a) k/2} \pmod {p^a} = 1^{k / 2} \pmod {p^a}$$ so it follows that $r$ divides $\varphi(p^a) / 2$ and thus, $2^d \nmid r$. But $k$ is odd with probability exactly half, so we are done. $\square$

From here, we note that if $N = p_1^{a_1} \cdots p_k^{a_k}$, then choosing a random element $x$ from $\mathbb{Z}_N^*$ is equivalent to choosing random elements $x_i$ from $\mathbb{Z}_{p_i^{a_i}}^*$ and mandating that $x = x_i \pmod {p_i^{a_i}}$ for all $i$. Let $r_i$ be the period of $x_i$ modulo $p_i^{a_i}$, and define $d_i$ to be such that $2^{d_i}$ is the largest power of two dividing $r_i$.

Let $r$ be the order of $x$ modulo $N$. The crucial claim, then, is that if $r$ is odd or $x^{r/2} \pmod N = -1$, then the $d_i$ must all be the same. Indeed, we can observe that $r_i \mid r$ for every $i$, because $$x^r = 1 \pmod N \implies x^r \pmod {p_i} = x_i^r \pmod {p_i} = 1 \pmod {p_i}$$ Now if $r$ is odd, then all the $r_i$ must be odd and thus $d_i = 0$ for all $i$. If $x^{r/2} \pmod N = -1$, then by the Chinese Remainder Theorem we must have $x_i^{r/2} = -1 \pmod {p_i^{a_i}}$ for all $i$. This implies that $r_i$ does not divide $r / 2$, for every $i$. In particular, this means that all the $d_i$ must be the same. If this weren't the case, say $d_j \geq d_k + 1$ for some $j$ and $k$, then since $2^{d_j}$ divides $r$, it would have to follow that $r = z \cdot 2^a \cdot 2^{d_k}$ for some integer $z$ and $a = d_j - d_k \geq 1$. Hence, it would follow that $2^{d_k}$ divides $r / 2$, a contradiction.

From here, we note that the probability that all of the $d_i$ are the same is worst (i.e. largest) when the same number $d$ is such that $2^d$ divides $p_i^{a_i}$ for every $i$. In this case however, the lemma dictates that a randomly chosen element from $\mathbb{Z}_{p_i^{a_i}}^*$ has order divisible by $2^d$ with probability half. Now the orders of $x_i$ modulo $p_i^{a_i}$ are chosen independently from one another, so this probability in the worst case is the probability that all of the orders $r_i$ are equivalent to $r_1$, which is $2^{1-m}$ (recall $m$ is the number of distinct prime factors of $N$). The result then follows. $\square$

In particular, this means that Shor's algorithm as commonly written can be applied to any number, and with constant probability of success, it will return a non-trivial factor of it! The probability of success is worst when $N$ is a semiprime (the lower bound on the probability of success is $1/2$) and tends arbitrarily closer to $1$ as the number of prime factors of $N$ increases.