Shor’s Factorization Algorithm

Shor’s factorization algorithm is one of the prime examples in which a quantum computer demonstrates enormous power surpassing its classical counterpart [1, 2]. Although the factorization algorithm may be carried out with a classical computer, it takes an exponentially longer time (i.e., practically impossible) compared to Shor’s quantum algorithm. Shor’s algorithm is almost identical with the classical one; it consists of a sequence of classical steps with one exception, which is replaced by a quantum algorithm. Our presentation here closely follows [3] and [4].