Motivation for Shor's Algorithm

The algorithm was viewed as important because the difficulty of factoring large numbers is relied upon for most cryptography systems. If an efficient method of factoring large numbers is implemented most of the current encryption schemes would be worthless. While it has not been proven that factoring large numbers can not be achieved on a classical computer in polynomial time, the fastest algorithm publicly available for factoring a large number $n$ (whose representation has $\lceil \log n \rceil$ bits) runs in $O(e^{c(\log n)^{1/3} * (\log \log n)^{2/3}})$, or exponential time. In contrast Shor's algorithm runs in $O((\log n)^{2} * \log \log n)$ on a quantum computer, and then must perform $O(\log n)$ steps of post processing on a classical computer. Overall then this time is polynomial. This discovery propelled the study of quantum computing forward, as such an algorithm is much sought after. (Shor)