On a quantum computer, to factor an integer formula_1, Shor's algorithm runs in polynomial time (the time taken is polynomial in formula_3, the size of the integer given as input). Specifically, it takes quantum gates of order formula_4 using fast multiplication, thus demonstrating that the integer-factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: formula_5. The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.