algorithm, and all three are instances of the hidden subgroup problem.

On a quantum computer, to factor an integer , Shor's algorithm runs in polynomial time, meaning the time taken is polynomial in . It takes quantum gates of order using fast multiplication, or even using the asymptotically fastest multiplication algorithm currently known due to Harvey and van der Hoeven,