AlegsaOnline.com

Shor's algorithm: quantum integer factoring and cryptography impact

Shor's algorithm is a quantum algorithm that factors integers and finds discrete orders in polynomial time, with important implications for public-key cryptography and the development of large-scale quantum computers.

Author: Leandro Alegsa Creation date: November 13, 2022 Last updated: May 25, 2026

en.wikipedia.org · CC BY 4.0

$N$ Shor's algorithm is a landmark quantum algorithm introduced by Peter Shor in the mid-1990s. It provides a method to factor large integers or, equivalently, to compute the order of an element modulo N. The algorithm showed that a sufficiently powerful quantum computer could solve an important problem much faster than known classical algorithms, raising profound practical and theoretical questions.

Problem and goal

The algorithm addresses integer factorization: given a composite number N, find nontrivial prime factors. This task—finding prime factors—is the basis of widely used public-key schemes. Shor transformed factoring into an instance of order-finding, which a quantum processor can solve efficiently by exploiting superposition and interference.

How it works (high level)

At a conceptual level the quantum part performs period or order finding using the quantum Fourier transform. After preparing superposed states and applying a modular exponentiation operation, a quantum measurement yields information about the period. That information is then processed classically to recover factors. The major logical steps are:

Reduce factoring to finding the order r of a random integer a modulo N.
Use a quantum circuit to create a superposition and compute periodic sequence values.
Apply the quantum Fourier transform and measure to obtain data related to r.
Use classical postprocessing (continued fractions, gcd) to extract factors.

Complexity and implications

Shor's algorithm runs in polynomial time in the number of digits of N, a dramatic improvement over the best known classical methods whose running time grows superpolynomially for large N. Because the security of widely deployed systems such as RSA and other public-key schemes depends on the practical difficulty of factoring, a fully scalable quantum computer running Shor's algorithm would undermine many current cryptographic systems and has driven interest in quantum-resistant alternatives.

History, experiments and limitations

Since its discovery, Shor's algorithm has been demonstrated on small numbers in laboratory quantum devices, but scaling to the sizes needed to break modern keys requires large, fault-tolerant quantum machines and significant error correction overhead. Progress in qubit quality, coherence times and scalable architectures remains essential before the algorithm poses a real threat to deployed cryptography.

Uses, distinctions and further reading

Beyond its immediate cryptographic implications, Shor's algorithm is a central example in the study of quantum algorithms and complexity theory, illustrating how quantum resources can change computational difficulty classes. The result has motivated work in post-quantum cryptography and in alternative quantum algorithms for problems like discrete logarithms. For introductory surveys and technical expositions see further resources.

Properties

The Shor algorithm is a probabilistic algorithm. In some, depending on the number of repetitions arbitrarily few, cases it leads to no result; the algorithm thus belongs to the class of Monte Carlo algorithms.

Input: A composite number .
Output: A nontrivial factor of .
Runtime: $O\left((\log \,n)^{3}\right)$ gate operations.

Expiration

The basic idea is that one can factorize back to the determination of the order. This determination can be done effectively using the quantum Fourier transform. One therefore often divides the algorithm into a classical part to reduce the problem and a quantum part that efficiently solves the residual problem.

Classic part

Choose a number with $1<x<n$ .
Determine the $ggT$ $(x$ , $n)$ (for example, using the Euclidean algorithm). If the result is not equal to 1, return this as the solution and terminate. Otherwise, proceed to the next step.
Using the quantum part (see below), determine the order of in the prime residue class group $({\mathbb Z}/n{\mathbb Z})^{\times }$ (the smallest $r\in {\mathbb {N}}$ , such that $x^{r}\equiv 1({\textrm {mod}}\;n)$ ). Step 2 ensured that such an exists.
Start over at 1 if:

is odd, or
$x^{{r/2}}\equiv -1({\textrm {mod}}\;n)$ .

Return ${\textrm {ggT}}(x^{{r/2}}-1,n)$ as the solution.

Solution in the last step

Consider the product ( $x^{{r/2}}-1$ ) - ( $x^{{r/2}}+1$ ) = $x^{r}-1$ . We know after step 3 that holds: $x^{r}-1\equiv 0\mod n$ , that it does not hold: $x^{r/2}+1\equiv \ 0\mod n$ (Step 4) and that does not hold: $x^{r/2}-1\equiv \ 0\mod n$ (step 3, since is the smallest number with $x^{r}-1\equiv \ 0\mod n$ and {r/2}<r holds), from which it follows that contains $x^{{r/2}}-1$ nontrivial divisors of ; the Euclidean algorithm for computing the $ggT$ yields these divisors in polynomial time.

Number of iterations for the partial invention

The probability of obtaining a divisor given a random choice of is at least $1-1/2^{{k-1}}$ , where the number of distinct prime factors of (not equal to 2). For example, if is composed of only two prime factors, one solution is obtained with probability 1/2 per pass, so the probability of failure after steps is only $2^{{-t}}$ .

Quantum Part

Determine as a power of 2 with $n^{2}\leq q<2n^{2}$ .
Initialize the first quantum register (input register) with the superposition (see qubit) of all states $a{\bmod {q}}$ ( is a number less than ). This leads to the state:
${\frac {1}{q^{{1/2}}}}\sum _{{a=0}}^{{q-1}}|a\rangle \ |0\rangle$ .
Initialize the second register (output register) with the superposition of the states $x^{a}{\bmod {n}}$ . The result is the state:
${\frac {1}{q^{1/2}}}\sum _{a=0}^{q-1}|a\rangle \ |x^{a}{\bmod {n}}\rangle$ .
On the first register, perform the quantum Fourier transform where:
$QFT\left(|a\rangle \right)={\frac {1}{q^{{1/2}}}}\sum _{{c=0}}^{{q-1}}e^{{2\pi iac/q}}\ |c\rangle$
such that results in:
${\frac {1}{q}}\ \sum _{a=0}^{q-1}\ \sum _{c=0}^{q-1}e^{2\pi iac/q}\ |c\rangle \ |x^{a}{\bmod {n}}\rangle$ .
Perform a measurement (take the contents of the registers). The probability for the state $\left|c,x^{k}{\bmod {n}}\right\rangle$ with is given by:
$\left|{\frac {1}{q}}\ \sum _{{a:x^{a}\equiv x^{k}}}e^{{2\pi iac/q}}\right|_{{}}^{2}$ . Here, the relation $a\equiv k\mod r$ or $a=br+k$ , so that we can write:
$\left|{\frac {1}{q}}\ \sum _{{b}}e^{{2\pi i\left(br+k\right)c/q}}\right|_{{}}^{2}$ By amplification, this discrete function has characteristic maxima for values of a variable $d\in {\mathbb {Z}}$ , which is the relation
$\left|{\frac {c}{q}}-{\frac {d}{r}}\right|\leq {\frac {1}{2q}}$ . It can be shown that for the given relations of $q,r$ and there is at most one such value at fixed Thus, computed if and are divisor-irrelevant. (The probability for this case is at least ϕ ${\frac {\phi (r)}{3r}}$ or Ω $\Omega \!\left({\frac {1}{\log \log r}}\right)$ , that is, we get with high probability after $O(\log \log r)$ repetitions).
Return the computed value $r^{\prime }$ if it is indeed the order of , otherwise repeat the experiment.