Can Shor's algorithm factor multi-prime numbers? I know that Shor's algorithm can factor semi-primes ($N = p \times q \space, \{p, \space q \in \Bbb{P} \space \vert \space p, \space q \gt 0 \} $).

Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?
Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod n$, then $\gcd(a^t \pm 1, n)$ is a nontrivial factor of $n$.  (Otherwise, repeat with another $a$.)  If $n = p q r$ and $\gcd(a^t \pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

The cost is dominated by $(\lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.


Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:


If a prime factor is bounded by $y$, then $\gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$—e.g., trial division, Pollard's $\rho$, ECM, etc.  If $n = p q r$ and you find $u$ so that $\gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

Grover's algorithm finds a preimage of 0 under $u \mapsto [\gcd(n, f(n, u)) = 1]$ in the time for about $\sqrt{y}$ quantum evaluations of $f$.  For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{\sqrt{\log y \log \log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.


Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.