Shor's Algorithm: Factoring Semi-Primes and Breaking RSA

Introduction to Shor's Algorithm

• Purpose: Shor's algorithm is designed to factor numbers of the form $n = pq$, specifically semi-primes.

• Significance: Semi-primes are critical for the security of the RSA cryptosystem, making Shor's algorithm a direct threat to current internet security if large-scale quantum computers are built.

• Classical Factoring Limitations: Prior best-known classical algorithms (e.g., trial division, Pollard's Rho) for factorinlutg a large number $n$ (product of two primes) are exponential or at least super-polynomial in the size of $n$ (where size $m = \log_2 n$ represents the number of bits of $n$).

• Quantum Advantage: Shor's algorithm on a quantum computer can solve this factoring problem in approximately $O(m^3)$ time. This stark difference means RSA is vulnerable to sufficiently large quantum computers.

• Algorithmic Paradigm: Shor's algorithm implements concepts like divide and conquer on a quantum computer, with the core operation being the Quantum Fourier Transform (QFT).

• Quantum Fourier Transform (QFT): This is the quantum analogue of the classical Fast Fourier Transform (FFT) and is central to Shor's algorithm. It was studied earlier in the course sequence (part of course three).

High-Level Steps of Shor's Algorithm

• Conversion to Order Finding: Shor's algorithm transforms the factoring problem into an order finding problem, which is a version of the discrete logarithm problem.

• Periodic Function: The algorithm relies on finding the unknown period of a periodic function. Quantum computers are particularly adept at this task.

• Pioneering Work: While called Shor's algorithm, it incorporates contributions from other works, such as quantum phase estimation by Kitaev.

• Impact: Shor's algorithm is the first known algorithm to demonstrate an exponential speedup on a quantum computer compared to classical computers for a significant problem, fueling immense interest and research in quantum computing.

• Post-Quantum Cryptography: The potential threat to RSA has spurred development in post-quantum cryptography, with solutions already being explored as of 2024.

Number Theory Basis (Classical Component)

• Goal: Given $n = pq$, where $p$ and $q$ are unknown primes, the objective is to find $p$ and $q$.

• Step 1: Choose a Random Integer $A$:

  • Select a random integer $A$ such that $1 < A < n$ and $GCD(A, n) = 1$.

  • Note: If $GCD(A, n) <br>eq 1$, then $A$ shares a factor with $n$, meaning we would have already found a factor like $p$ or $q$. However, the probability of this happening for a large $n$ is extremely low.

• Step 2: Explore Powers of $A$ Modulo $n$:

  • Examine the sequence: $A^1 \bmod n, A^2 \bmod n, A^3 \bmod n, ext{…}$.

  • Periodicity: Since $A$ is relatively prime to $n$, $A^x \bmod n$ can never be $0$. As there are only $n$ possible residues ($1$ to $n-1$), the sequence must eventually repeat.

  • If $A^i \bmod n ext{ is the same as } A^{i+j} \bmod n$, then due to $GCD(A, n) = 1$ (implying $A$ has a multiplicative inverse modulo $n$), it must be that $A^j \bmod n = 1$. This signifies a periodic sequence.

• Definition of Order ($R$):

  • The order of $A$ modulo $n$, denoted as $R$, is the smallest positive integer ($R > 0$) such that $A^R \bmod n = 1$ .

• Examples with $n=15$:

  • Example 1: Let $A=4$.

    • $4^1 \bmod 15 = 4$

    • $4^2 \bmod 15 = 16 \bmod 15 = 1$

    • The order of $4$ modulo $15$ is $R = 2$.

  • Example 2: Let $A=7$.

    • $7^1 \bmod 15 = 7$

    • $7^2 \bmod 15 = 49 \bmod 15 = 4$

    • $7^3 \bmod 15 = (4 imes 7) \bmod 15 = 28 \bmod 15 = 13$

    • $7^4 \bmod 15 = (13 imes 7) \bmod 15 = 91 \bmod 15 = 1$

    • The order of $7$ modulo $15$ is $R = 4$.

  • Example 3: Let $A=11$.

    • $11^1 \bmod 15 = 11$

    • $11^2 \bmod 15 = 121 \bmod 15 = 1$

    • The order of $11$ modulo $15$ is $R = 2$.

Factoring $n$ Using the Order $R$ (Classical Success Conditions)

• Premise: If we can find the order $R$ of $A$ modulo $n$ (where $A^R \bmod n = 1$), we can potentially find a factor of $n$.

• Condition 1: $R$ must be an even number.

  • If $R$ is even, we can write $R = 2T$ for some integer $T$.

  • Then $A^{2T} \bmod n = 1$, which implies $(A^T)^2 \bmod n = 1$.

  • Rewriting, we get $(A^T)^2 - 1 \bmod n = 0$, or $(A^T - 1)(A^T + 1) \bmod n = 0$.

• Condition 2: $A^T - 1 ot\bmod n = 0$.

  • This condition is crucial. It is guaranteed by the definition of $R$ as the smallest positive integer such that $A^R \bmod n = 1$. If $A^T - 1 \bmod n = 0$, then $A^T \bmod n = 1$. Since $T = R/2$ and $T < R$, this would contradict $R$ being the smallest order.

• Factoring Step: If both conditions are met (i.e., $R$ is even AND $A^{R/2} + 1 ot\bmod n = 0$), then $GCD(A^{R/2} + 1, n)$ will yield a non-trivial factor of $n$ (either $p$ or $q$).

  • This works because $(A^{R/2} - 1)(A^{R/2} + 1)$ is a multiple of $n=pq$, and neither $A^{R/2}-1$ nor $A^{R/2}+1$ is a multiple of $n$. Thus, $p$ (or $q$) must divide one term, and $q$ (or $p$) must divide the other.

• Probability of Success: For a randomly chosen coprime $A$, the probability that $R$ is even AND $A^{R/2} + 1 <br>ot\bmod n = 0$ is typically greater than $0.5$. Repeated trials with different $A$ values significantly increase the chances of success.

• Example with $n=15, A=7$:

  • Order $R=4$, which is even. $T = R/2 = 2$.

  • $A^T - 1 = 7^2 - 1 = 49 - 1 = 48$. $48 <br>ot\bmod 15 = 0$. So Condition 2 holds.

  • $A^T + 1 = 7^2 + 1 = 49 + 1 = 50$. $50 \bmod 15 = 5$. This is not $0$. So $A^{R/2} + 1 <br>ot\bmod n = 0$ holds.

  • $GCD(50, 15) = GCD(5, 15) = 5$. A factor (5) successfully pops out.

• Example with $n=15, A=11$:

  • Order $R=2$, which is even. $T = R/2 = 1$.

  • $A^T - 1 = 11^1 - 1 = 10$. $10 <br>ot\bmod 15 = 0$.

  • $A^T + 1 = 11^1 + 1 = 12$. $12 <br>ot\bmod 15 = 0$.

  • $GCD(12, 15) = 3$. A factor (3) successfully pops out.

The Quantum Advantage: Finding the Order $R$

• Classical Difficulty: Classically, finding the order $R$ of $A$ modulo $n$ is computationally hard. The best classical approach is to compute powers $A^1, A^2, ext{…}$ until $1$ is found, which can take up to $R$ steps. Since $R$ can be comparable in size to $n$, this problem is as hard as factoring itself and is related to the discrete logarithm problem.

• Quantum Solution: Shor's algorithm provides a quantum component specifically for order finding. Given $A$ and $n$, the quantum algorithm can find $R$ with very high probability in polynomial time (in the number of bits of $n$).

• Overall Efficiency: This efficient quantum order-finding step, combined with the successful classical steps, allows Shor's algorithm to factor $n$ in polynomial time on a quantum computer, making it exponentially faster than any known classical factoring algorithm.