Shor's algorithm is used to find prime factors of an integer. On a quantum computer, Shor's algorithm runs in polynomial time and is almost exponentially faster than the most efficient known classical factoring algorithm.

<!--
[metadata-name]: Shor's Algorithm
[metadata-tags]: Textbook
[metadata-url]: https://github.com/aws-samples/amazon-braket-algorithm-library/blob/main/src/braket/experimental/algorithms/shors
-->