# Shor's algorithm Shor's algorithm is a [[Quantum computing|quantum algorithm]] for finding the prime factors of an integer. ## The algorithm The algorithm consists of two parts: - A classical reduction of the problem to the *order-finding problem*: given $a,N$ which are co-prime, find the order of $a$ in the multiplicative group modulu $N$, i.e. the minimal $r$ such that $a^{r} \equiv 1 \mod N$. - A quantum subrutine solving the order-finding problem. After eliminating easy cases, the algorithm can be stated as follows. Let $N$ be odd, and not a prime power. We want to output two nontrivial factors of $N$ . 1. Pick a random number $1 < a < N$ . 2. Compute $K = \gcd ( a , N )$ , the greatest common divisor of $a$ and $N$ . 3. If $K ≠ 1$ , then $K$ is a nontrivial factor of $N$ , with the other factor being $N / K$ , and we are done. 4. Otherwise, use the *quantum subroutine* to find the order $r$ of $a$, 5. If $r$ is odd, then go back to step 1. 6. Compute $g = \gcd ( N , a^{r / 2} + 1 ) +1)$. If $g$ is nontrivial, the other factor is $N / g$ , and we're done. Otherwise, go back to step 1. It has been shown that this will be likely to succeed after a few runs. ### Quantum subroutine *Quantum stuff* ### How many qubits? Let $n = ⌈ log_{2} ⁡ N ⌉$ (the smallest integer $n$ such that $N \leq 2^{n}$). Shor's algorithm uses a quantum circuit involving two registers, one requires $n$ qubits, the one at least $2n$ qubits to reach sufficient accuracy. Current advancements show that factoring an $n$-bit integer would require $2n+3$ logical qubits. ## Links https://www.classiq.io/insights/shors-algorithm-explained