# Arduous Factorization

Let’s discuss the preliminaries necessary for understanding Shor's Algorithm. We start with describing the factoring problem and its classical solution.

**Shor’s Algorithm** was proposed by the American mathematician Peter Shor in 1994, and it promises prime factorization of numbers in **polynomial** time. This might seem like an easy problem, at first. After all, we learned the procedure for representing a number as a product of its prime factors in secondary school. Following the same process, we know that we can break down a number, let’s say $15$, into its prime factors as $15 = 3\times5$ or another number, let’s say $1748$, as $1748=2^{2}\times19^{1}\times23^{1}$.

It turns out that this problem is not that easy to do with larger numbers. In fact, the time complexity of our fastest and most efficient classical algorithms for prime factorization is **exponential**. Specifically, the **general number field sieve** algorithm, which is the fastest known algorithm for factoring numbers larger than a **googol** ($10^{100}$), takes $O(\exp{1.9(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}})$ to factor an integer $N$.

As Peter Shor discovered in 1994, quantum computers can solve this problem much faster. In fact, **Shor’s Algorithm** provides an **exponential** speedup over its classical counterpart. Specifically, it gets rid of the exponential term and has an overall asymptotic time complexity of order $O((\log
{N}^{2}(\log\log N)(\log \log \log N)))$ or $\approx O(N^{3})$, roughly **cubic** time complexity.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy