Shor's Algorithm | Factoring Integers with Exponential Speedup
Quick Technical Answer:
Shor's algorithm is a quantum algorithm that factors integers in polynomial time O((log N)³), providing an exponential speedup over the best classical algorithm (General Number Field Sieve). It solves order-finding using the Quantum Fourier Transform.
Formula / Unitary:
f(x) = a^x \pmod{N}, \quad r \text{ such that } a^r \equiv 1 \pmod{N}
Simulate this in Itachi Quantum Studio
Inspect state amplitudes, 3D Bloch sphere vector, and OpenQASM code live.
Quantum Order-Finding Core
The cryptographic hardness of RSA relies on the difficulty of factoring the product of two large primes N = pq. Shor proved that factoring reduces to finding the period r of the function f(x) = a^x mod N. While classical algorithms require sub-exponential time exp(O((log N)^(1/3))), a quantum computer determines r in polynomial time using Quantum Phase Estimation (QPE) and the Inverse Quantum Fourier Transform (IQFT).
Factoring Complexity Comparison
| Algorithm | Type | Complexity Class | Time Complexity for n-bit integer |
|---|---|---|---|
| Number Field Sieve (GNFS) | Classical | Sub-Exponential | O(exp((c n)^(1/3) (log n)^(2/3))) |
| Trial Division | Classical | Exponential | O(2^(n/2)) |
| Shor's Quantum Algorithm | Quantum (BQP) | Polynomial | O(n² log n log log n) |
Frequently Asked Questions
How many qubits does Shor's algorithm require to break RSA-2048?
To factor RSA-2048, Shor's algorithm requires approximately 4,098 logical qubits. With surface code error correction, this translates to roughly 4 to 20 million physical qubits depending on physical gate error rates.