We present a quantum algorithm for factoring products of prime numbers which exploits Grover search to factor any n-bit biprime using 2n-5 qubits or less. The algorithm doesn’t depend on any properties of the number to be factored, has guaranteed convergence, and doesn’t require complex classical pre or post-processing. Large scale simulations confirm a success probability asymptotically reaching 100% for > 800 random biprimes with 5 < n < 35 (corresponding to 5 – 65 qubits) with the largest being 30398263859=7393*4111763. We also present a variant of the algorithm based on digital adiabatic quantum computing and show that Grover based factorization requires quadratically fewer iteration steps in most cases.
