{"history":[],"article":{"id":"75884ddf-a790-4100-9369-1249dc786b86","title":"Shor's algorithm","slug":"shor-s-algorithm","content":":::summary\n:::\n\n# \n**Shor's algorithm** is a [quantum algorithm](https://bliptext.com/articles/quantum-algorithm) for finding the [prime factors](https://bliptext.com/articles/prime-factor) of an integer.\nIt was developed in 1994 by the American mathematician [Peter Shor](https://bliptext.com/articles/peter-shor).\nIt is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms.\nOn the other hand, factoring numbers of practical significance requires far more [qubits](https://bliptext.com/articles/qubit) than available in the near future.\nAnother concern is that noise in quantum circuits may undermine results, requiring additional qubits for [quantum error correction](https://bliptext.com/articles/quantum-error-correction).\nShor proposed multiple similar algorithms for solving the [factoring problem](https://bliptext.com/articles/integer-factorization), the [discrete logarithm problem](https://bliptext.com/articles/discrete-logarithm), and the period-finding problem.\n\"Shor's algorithm\" usually refers to the factoring algorithm, but may refer to any of the three algorithms.\nThe discrete logarithm algorithm and the factoring algorithm are instances of the period-finding algorithm, and all three are instances of the [hidden subgroup problem](https://bliptext.com/articles/hidden-subgroup-problem).\nOn a quantum computer, to factor an integer N, Shor's algorithm runs in [polynomial time](https://bliptext.com/articles/polynomial-time), meaning the time taken is polynomial in \\log N. It takes [quantum gates](https://bliptext.com/articles/quantum-logic-gate) of order using fast multiplication, or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and [Van Der Hoven](https://bliptext.com/articles/van-der-hoven),

History