Shor’s Algorithm

Shor’s algorithm, introduced by Peter Shor in 1994 (algorithms for quantum computation: discrete logarithms and factoring), is the breakthrough quantum algorithm that factors large integers in polynomial time, a task widely believed to be intractable for classical computers. Given an integer $N$ , the algorithm finds its prime factors in $O\left((\log N)^2 (\log \log N)(\log \log \log N)\right)$ time on a quantum computer. This is exponentially faster than the best classical algorithms, such as the general number field sieve, which runs in sub-exponential time $O\left(e^{c (\log N)^{1/3} (\log \log N)^{2/3}}\right)$ , where $c = \frac{1}{3}(92 + 26\sqrt{13})^{1/3}$ .

The discovery of Shor’s algorithm showed that a large quantum computer would be capable of breaking widely used public-key cryptosystems, most notably RSA, whose security relies on the assumed hardness of integer factorization. This result initiated both the global effort to build scalable quantum computers and the rapid development of post-quantum cryptography, which seeks cryptographic protocols secure even against quantum attackers.

RSA Cryptosystem

Since Shor’s algorithm was primarily designed to break the RSA public-key cryptosystem. For completeness, we first review the core principles of RSA. The RSA cryptosystem, along with its variants, is one of the most widely deployed methods for securely transmitting messages over public channels, such as the Internet, where it protects confidentiality and enables digital signatures. Its security relies fundamentally on a single, long-standing computational assumption: that factoring a large composite integer into its prime factors is extraordinarily difficult for classical computers.

It is worth emphasizing that testing whether a number is prime is computationally feasible, whereas factoring a large composite number into its prime factors remains extraordinarily difficult. RSA cryptography leverages precisely this asymmetry: while anyone can efficiently verify the primality of the factors used in key generation, recovering those factors from the public modulus is, for classical computers, practically intractable. This one-way computational difficulty forms the cornerstone of RSA’s security, enabling secure encryption and decryption of messages.

The RSA cryptosystem operates as follows:

Alice prepares two very large prime numbers $p$ and $q$ , which she keeps secret. She computes $N = pq$ and publishes $N$ . She also chooses a number, called the public exponent (or encoding exponent), $e < N$ , which is required to be relatively prime to $(p-1)(q-1)$ , that is, $\mathbf{gcd}(e,(p-1)(q-1)) = 1$ . Alice then computes the multiplicative inverse of $e$ modulo $(p-1)(q-1)$ , namely a number $d$ satisfying

$de \equiv 1 \pmod{(p-1)(q-1)}$

She keeps $d$ secret, thus called the secret exponent (or decoding exponent).

When Bob wants to send a message to Alice, he first encodes the message as an integer $m$ with $m < N$ . He encrypts it as

$M = m^{e} \pmod{N}$

Upon receiving $M$ , Alice decrypts it using

$m \equiv M^{d} \pmod{N}$

where $d$ is the multiplicative inverse of the public exponent $e$ modulo $(p-1)(q-1)$ .

To see that the RSA cryptosystem correctly recovers the message $m$ using $m \equiv M^{d} \pmod{N}$ , we need to check

$m \equiv (m^e)^{d} \pmod{N}$ .

From $de \equiv 1 \pmod{(p-1)(q-1)}$ , there exists an integer $k$ such that $de = k (p-1)(q-1) + 1$ . Hence

$(m^e)^{d} = m \bigl[ m^{k(q-1)} \bigr]^{p-1}$ .

Suppose $m$ is not a multiple of $p$ . Fermat’s little theorem gives

$\bigl[ m^{k(q-1)} \bigr]^{p-1} \equiv 1 \pmod{p}$ .

If $m$ is a multiple of $p$ , then $m^{de} \equiv 0 \pmod{p}$ .

Similarly,

$\bigl[ m^{k(p-1)} \bigr]^{q-1} \equiv 1 \pmod{q}$

when $m$ is not a multiple of $q$ , and $m^{de} \equiv 0 \pmod{q}$ if $m$ is a multiple of $q$ .

We now verify $m^{de} \equiv m \pmod{N}$ by considering several cases.

If $m$ is a multiple of both $p$ and $q$ , then it is automatically a multiple of $N = pq$ , and $m^{de} \equiv m \pmod{N}$ holds trivially.
If $m$ is a multiple of $p$ but not of $q$ , then

$m \equiv 0 \pmod{p}, \quad m^{de} \equiv 0 \pmod{p}$ ,

and

$\bigl[m^{k(p-1)}\bigr]^{q-1} \equiv 1 \pmod{q}$ .

Hence,

$m^{de} \equiv m \pmod{q}, \quad m^{de} \equiv m \pmod{p}$ .

By the Chinese remainder theorem ${}^1$ ,

$m^{de} \equiv m \pmod{N}$ .

We are using a basic consequence of the Chinese remainder theorem: if two integers $a$ and $b$ satisfy $a \equiv b \pmod{p}$ and $a \equiv b \pmod{q}$ , with $\gcd(p,q) = 1$ , then $a \equiv b \pmod{pq}$ . In particular, if $p$ and $q$ are prime, it is easier to see $p \mid (a-b)$ and $q \mid (a-b)$ implies $pq \mid (a-b)$ .

If $m$ is a multiple of $q$ but not of $p$ , the argument is symmetric, giving

$m^{de} \equiv m \pmod{N}$ .

If $m$ is not a multiple of either $p$ or $q$ , then Fermat’s little theorem gives

$m^{de} \equiv m \pmod{p}, \quad m^{de} \equiv m \pmod{q}$ .

Again, by the Chinese remainder theorem,

$m^{de} \equiv m \pmod{N}$ .

This completes the proof of $m^{de} \equiv m \pmod{N}$ .

We see from the above analysis that if one could factor $N$ efficiently, then the RSA system would be completely compromised. Indeed, factoring $N$ reveals the primes $p$ and $q$ , from which one can compute $(p-1)(q-1)$ , determine the public exponent $e$ , and then recover the secret exponent $d$ . With $d$ in hand, any encrypted message can be decrypted.

Shor’s Algorithm

Definition (The Factoring Problem)
The input to Shor’s algorithm is an odd composite integer $N = p q$ , where $p$ and $q$ are distinct large primes. The goal is to find the prime factors $p$ and $q$ .

Shor’s algorithm is a hybrid quantum-classical algorithm that factors $N$ in polynomial time on a quantum computer. It consists of two main phases:

Classical reduction: Transform factoring $N$ into an instance of the order-finding problem (see this post).
Quantum order-finding: Solve the order-finding problem efficiently using a quantum computer.

The classical reduction (which succeeds with probability $> 1/2$ for random choices) is as follows:

1. Choose a random integer $a \in {2, 3, \dots, N-1}$ and compute $d = \gcd(a, N)$ :

If $1 < d < N$ , then $d$ is a non-trivial factor of $N$ . Factoring complete.
If $d = 1$ , continue.

2. Find the multiplicative order $r$ of $a$ modulo $N$ , i.e., the smallest positive integer $r$ such that
$a^r \equiv 1 \pmod{N}$ .

3. If $r$ is odd, return to the first step with a new $a$ .

4. If $r$ is even, compute $b = a^{r/2} \mod N$ :

If $b \equiv -1 \pmod{N}$ , return to the first step.
If $b \not\equiv \pm 1 \pmod{N}$ , proceed.

5. Compute the factors:
$p = \gcd(b - 1, N)$ , $q = \gcd(b + 1, N)$ .
At least one of these is a non-trivial factor of $N$ .

The only step that is computationally infeasible on a classical computer is step 2: finding the order $r$ .
Shor’s breakthrough contribution is a quantum algorithm that performs this order-finding step in polynomial time using quantum phase estimation on the unitary operator $x \mapsto a x \mod N$ .

Once $r$ is obtained quantumly, the remaining classical post-processing immediately yields the prime factors $p$ and $q$ . Thus, on a sufficiently large fault-tolerant quantum computer, Shor’s algorithm solves the integer factorization problem efficiently, rendering RSA and related cryptosystems insecure.

Remark (Why the Reduction Works)

Assume that $r$ is even and that $a^{r/2} \not\equiv -1 \pmod{N}$ (the cases explicitly filtered out by the algorithm). Since $r$ is the order of $a$ modulo $N$ , we have
$a^r \equiv 1 \pmod{N}$ .
This implies
$a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}$ ,
so $N \mid (a^{r/2} - 1)(a^{r/2} + 1)$ , or equivalently,
$pq \mid (a^{r/2} - 1)(a^{r/2} + 1)$ .

Because $p$ and $q$ are distinct primes, the prime factors of the product $(a^{r/2}-1)(a^{r/2}+1)$ can be distributed in only four logical ways:

$p$ divides $a^{r/2}-1$ and $q$ divides $a^{r/2}+1$
$p$ divides $a^{r/2}+1$ and $q$ divides $a^{r/2}-1$
$pq$ divides $a^{r/2}-1$ (i.e., $N$ divides $a^{r/2}-1$ )
$pq$ divides $a^{r/2}+1$ (i.e., $N$ divides $a^{r/2}+1$ )

Cases 1 and 2 are precisely what we want: they yield non-trivial factors via the gcd computations
$p = \gcd(a^{r/2}-1, N)$ and $q = \gcd(a^{r/2}+1, N)$ (or vice versa).
Cases 3 and 4, however, must be excluded:

Case 3 is impossible: If $N$ divides $a^{r/2}-1$ , then $a^{r/2} \equiv 1 \pmod{N}$ .
But $r$ is the order of $a$ modulo $N$ , so $r$ would have to divide $r/2$ , which is impossible unless $r = 0$ , a contradiction.
Case 4 is impossible under our assumption: If $N$ divides $a^{r/2}+1$ , then $a^{r/2} \equiv -1 \pmod{N}$ .
This situation is explicitly detected and rejected in the algorithm (step 5).

Thus, whenever the algorithm reaches step 6, we are guaranteed to be in Case 1 or Case 2, and the two gcd operations recover the prime factors $p$ and $q$ of $N$ .

Example

Let us illustrate Shor’s algorithm with the integer $N = 15$ .

Choose a random number: Let $a = 7$ . Compute $\gcd(7, 15) = 1$ .
Since $\gcd(7, 15) = 1$ , we proceed to the next step.
Find the period $r$ : Using a quantum computer, we determine the period of the function
$f(x) = 7^x \bmod 15$ .
The result is $r = 4$ , since $7^4 \equiv 1 \pmod{15}$ .
Use the period to find the factors:
- Since $r = 4$ is even, compute $7^{r/2} - 1 = 7^2 - 1 = 48$ .
- Compute the gcd: $\gcd(48, 15) = 3$ , which is one factor of $15$ .
- Similarly, $7^{r/2} + 1 = 7^2 + 1 = 50$ , and $\gcd(50, 15) = 5$ , which is the other factor.