Factoring Blum integers ∈ BQP (Shor)

Inclusion · quantum setting · Shor97

Statement

Factoring Blum integers is in BQP: Shor’s quantum algorithm finds, with constant probability and in polynomial time, a nontrivial factor of every odd composite $N$ that is not a prime power, Blum integers in particular — Shor97.

Notes

• A factorization of $N$ decides quadratic residuosity modulo $N$ by Euler’s criterion modulo $p$ and $q$ (QR ⇒ FAC), so QR is in $\mathbf{BQP}$ as well — standard.
• The same algorithm places general factoring in BQP: FAC ∈ BQP — Shor97.