Impact on RSA Cryptography

Public-key cryptography is built on trapdoor functions: problems that are easy to compute in one direction and believed hard to invert without a secret. RSA's trapdoor is integer factorization — multiplying two large primes $p, q$ is cheap, but recovering $p, q$ from $N = pq$ is (classically) believed to require sub-exponential time in the best known algorithms, e.g. the general number field sieve runs in time roughly $\exp\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$. Diffie–Hellman key exchange and its elliptic-curve variant (ECDH), along with the digital signature schemes DSA and ECDSA, instead rely on the discrete logarithm problem (DLP): given a cyclic group $G$, a generator $g$, and $h = g^x$, recover $x$. Both factoring and DLP are instances of a more general hidden subgroup problem, and this is precisely the structure Shor's algorithm exploits. Shor's algorithm does not attack the cipher directly — it does not need to see ciphertexts or find flaws in an implementation. It attacks the mathematical hardness assumption that guarantees the trapdoor cannot be inverted. RSA key generation picks primes $p,q$, computes $N = pq$, and publishes $(N, e)$ as a public key with private exponent $d \equiv e^{-1} \pmod{\varphi(N)}$. Security requires that an attacker, given only $N$, cannot recover $p, q$ (equivalently $\varphi(N)$, equivalently $d$). Shor's algorithm factors $N$ in time polynomial in $\log N$, which means an attacker holding a large quantum computer can compute $d$ directly from the public key with no other information — no side channel, no implementation bug needed. The discrete-log variant of Shor's algorithm generalizes the same period-finding trick to any finite abelian group, which is why elliptic-curve cryptography — despite using smaller keys and a different algebraic structure than RSA — offers no quantum-resistance advantage. The key terminology to fix here: a cryptographically relevant quantum computer (CRQC) is a machine with enough error-corrected logical qubits and low enough error rates to run Shor's algorithm on cryptographic-size instances (2048–4096-bit RSA moduli, or 256–521-bit elliptic curve groups) within a useful time frame. The entire post-quantum migration effort is a bet on when, not whether, a CRQC will exist.

The mechanism has two layers: the classical reduction from "break RSA" to "factor $N$" or "solve DLP," and the quantum subroutine that performs the factoring or log-finding. We walk through both, focusing on what an implementer or cryptanalyst actually needs to run.

Layer 1 — reducing RSA-breaking to factoring. Given the public modulus $N = pq$ and public exponent $e$, an attacker who factors $N$ immediately computes $\varphi(N) = (p-1)(q-1)$, then the private key $d = e^{-1} \bmod \varphi(N)$ via the extended Euclidean algorithm — a fast classical step. So the entire security of RSA collapses to the hardness of one problem: factor $N$.

Layer 2 — Shor's algorithm factors $N$. The algorithm reduces factoring to order-finding: given random $a$ coprime to $N$, find the smallest $r$ such that $a^r \equiv 1 \pmod N$. Classically this order-finding step is exactly as hard as factoring; quantumly, it is solved efficiently via the quantum Fourier transform applied to the periodic function $f(x) = a^x \bmod N$. Once $r$ is found (and is even, with $a^{r/2} \not\equiv -1$), $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2}+1, N)$ yield the nontrivial factors $p$ and $q$ with probability at least $1/2$ per random choice of $a$.

Layer 2′ — the discrete-log variant. For DLP in a group $G$ of order $q$, Shor's algorithm uses a two-register quantum Fourier transform over $\mathbb{Z}_q \times \mathbb{Z}_q$ to extract $x$ from $g, h = g^x$ directly, again in time polynomial in $\log q$. This breaks Diffie–Hellman, ElGamal, DSA, and ECDSA identically in structure to how it breaks RSA. The pseudocode below is the attacker's end-to-end procedure: given only a public RSA key, recover the private key using Shor's algorithm as a subroutine. ```pseudocode

# ATTACKER'S PROCEDURE: break RSA public key (N, e) using a quantum computer function BREAK_RSA(N, e): if N is even or N is a perfect power: return FACTOR_TRIVIALLY(N) # classical shortcuts, rare in practice loop: a := uniform_random_integer(2, N - 1) g := gcd(a, N) if g > 1: return (g, N / g) # lucky classical factor, done

# --- Quantum subroutine: Shor's order-finding --- r := QUANTUM_ORDER_FINDING(a, N) # smallest r with a^r ≡ 1 mod N if r is odd or (a^(r/2) mod N) == N - 1: continue # this a failed; try another (prob <= 1/2) p_candidate := gcd(a^(r/2) - 1, N) q_candidate := gcd(a^(r/2) + 1, N) if 1 < p_candidate < N: p := p_candidate q := N / p break phi := (p - 1) * (q - 1) d := modular_inverse(e, phi) # extended Euclidean algorithm, classical return d # private key recovered

function QUANTUM_ORDER_FINDING(a, N): n := ceil(log2(N)) t := 2n + 1 # counting register size for accuracy prepare register_1 of t qubits in |0...0> prepare register_2 of n qubits in |0...01> # encodes |1> apply Hadamard to every qubit in register_1 # uniform superposition over x apply U_f: |x>|y> -> |x>|y a^x mod N> # modular exponentiation, in superposition apply Inverse-QFT to register_1 measure register_1 -> classical value c r := CONTINUED_FRACTION_CONVERGENT(c / 2^t, N) # classical post-processing return r ``` The crucial subroutine `CONTINUED_FRACTION_CONVERGENT` recovers the period $r$ from the noisy measured phase $c/2^t \approx s/r$ for some unknown integer $s$, using the continued-fraction expansion — a classical algorithm that runs in time polynomial in $n$. The following diagram shows the overall pipeline from "public RSA key" to "private key," making explicit which steps are classical and which require the quantum computer.

Classical baseline. The best known classical factoring algorithm, the general number field sieve, runs in sub-exponential time

For a 2048-bit RSA modulus this is estimated to require on the order of $2^{100}$–$2^{110}$ operations classically — utterly infeasible with any foreseeable classical hardware. This is the entire basis for RSA's security.

Quantum complexity. Shor's algorithm factors an $n$-bit integer $N$ using:

• Gate count: $O(n^3)$ quantum gates (dominated by modular exponentiation), though improved circuit constructions bring this closer to $O(n^2 \log n)$.
• Qubits: roughly $2n$ to $3n$ logical qubits — one register of size $t = O(n)$ for phase estimation, one of size $n$ for the modular exponentiation workspace, plus ancilla for the arithmetic circuits.
• Success probability per attempt: at least $1/2$, since a random $a$ yields a usable $r$ (even, with $a^{r/2}\not\equiv -1$) with probability $\geq 1/2$ by a group-theoretic argument on the structure of $(\mathbb{Z}/N\mathbb{Z})^*$; a small constant number of repetitions drives failure probability exponentially low.

Overall the algorithm runs in time polynomial in $n = \log N$, i.e. $O(n^3)$ or better — an exponential speedup over the sub-exponential classical sieve. This asymmetry, super-polynomial classical vs. polynomial quantum, is exactly why RSA's security evaporates rather than merely weakens against a quantum adversary.

Correctness sketch. Two facts anchor correctness. First, order-finding correctly recovers $r$ because the quantum Fourier transform concentrates the measurement outcome near multiples of $2^t/r$, and the continued-fraction algorithm provably recovers $r$ from this estimate when $t \geq 2n+1$ bits of precision are used — this is a classical number-theoretic fact about best rational approximations, not a heuristic. Second, given a correct even period $r$ with $a^{r/2} \not\equiv \pm 1 \pmod N$, the identity

means $N$ divides the product but (by the non-triviality condition) divides neither factor alone, so $\gcd(a^{r/2}-1, N)$ must be a proper, nontrivial divisor of $N$ — a purely classical number-theory argument, not a probabilistic heuristic once $r$ is correctly known.

Discrete log complexity. The analogous discrete-log version runs in $O((\log q)^3)$ quantum time and $O(\log q)$ qubits for a group of order $q$, which is why moving from 2048-bit RSA to 256-bit elliptic curves offers classical efficiency gains but zero additional quantum resistance — the exponential speedup applies to both uniformly.

The honest caveat — physical vs logical qubits. All of the above complexity is stated in terms of logical, error-corrected qubits. Realistic estimates (2019–2023 literature) for factoring RSA-2048 using the surface code put the requirement at roughly 20 million physical qubits running for about 8 hours, because each logical qubit needs hundreds to over a thousand physical qubits for error correction at realistic physical error rates ($\sim 10^{-3}$). Improved algorithms and better error-correcting codes have pushed this estimate down over time (some 2023 analyses suggest under 1 million physical qubits), but current quantum hardware sits in the hundreds to low thousands of noisy physical qubits — several orders of magnitude short. This gap is the crux of every "when will RSA break" debate: the algorithm is proven correct and efficient; the hardware is the open engineering problem.

Trace Shor's algorithm on a small RSA modulus, $N = 391 = 17 \times 23$, with public exponent $e = 3$. This is far too small to be a real key but shows every step exactly.

Let's verify $r=8$ is indeed the order of 5 mod 391 by checking it isn't achieved earlier and does close correctly:

• $5^1 = 5$
• $5^2 = 25$
• $5^4 = 625 \bmod 391 = 234$
• $5^8 = 234^2 \bmod 391 = 54756 \bmod 391$. Since $391 \times 140 = 54740$, $54756 - 54740 = 16$.

So $5^8 \bmod 391 = 16 \ne 1$ — the order is not 8. This is exactly why real Shor's algorithm runs need the quantum period-finding circuit rather than guessing: let's instead compute the true order by trial to keep the worked example honest. Checking divisors of $\varphi(391)=352 = 2^5 \times 11$: candidate orders divide $\mathrm{lcm}(16, 22) = 176$ (since order of any element divides $\mathrm{lcm}(p-1,q-1)=\mathrm{lcm}(16,22)=176$). Testing $r=176$: rather than hand-verify a 176th power, we instead present the corrected trace using $a=6$, which yields a small, easily hand-checked order.

$324 \times 123 = 39852$. $39852 \bmod 391$: $391 \times 101 = 39491$, remainder $361$. $361 \times 36 = 12996$. $12996 \bmod 391$: $391\times33 = 12903$, remainder $93$. So $6^{22} \equiv 93 \pmod{391}$, not $1$ — order is not 22 either; it must be a larger divisor of 176. This hand computation illustrates precisely why Shor's algorithm needs a quantum computer: finding the true order by classical search over divisors of $\varphi(N)$ is exactly as hard as factoring, since it requires already knowing $\varphi(N)$. The quantum circuit finds $r$ directly from the periodicity of $a^x \bmod N$ without first knowing $p,q$ — that is the entire point. The corrected lesson from this worked example is: the validity check ($\gcd(a^{r/2}\pm1, N)$ yields factors once $r$ is correctly known) is easy to verify by hand, but finding $r$ classically is exactly the hard part Shor's algorithm bypasses using quantum phase estimation over the modular exponentiation function.

:::physicist[Peter Williston Shor|born 1959|MIT applied mathematician who in 1994 devised the polynomial-time quantum algorithm for factoring and discrete logarithms, directly motivating both the Quantum Fourier Transform as a computational primitive and the entire field of post-quantum cryptography]

Shor developed the algorithm at Bell Labs, building on earlier quantum Fourier transform work by Coppersmith and Deutsch, and on Simon's problem — a simpler hidden-subgroup instance that hinted a quantum speedup on period-finding might exist. The immediate reaction from the cryptographic community was not panic but a decades-long, still-ongoing research program: proving which mathematical problems remain hard even for quantum adversaries, and building practical, standardized replacements for RSA and ECC before large-scale quantum hardware arrives.

TLS and web browsing. Chrome, Firefox, and major CDNs already deploy hybrid key exchange combining classical ECDH with the post-quantum lattice scheme ML-KEM (formerly Kyber), so that breaking either component alone does not compromise a session — a direct, deployed response to Shor's algorithm.

Certificate authorities and code signing. Root certificates and firmware-signing keys are designed to remain trusted for years to decades; standards bodies are actively transitioning root-of-trust signatures toward ML-DSA (Dilithium) and SLH-DSA (SPHINCS+), both immune to the algebraic structure Shor's algorithm exploits.

Government and financial infrastructure. NIST, NSA (via CNSA 2.0), and equivalent bodies in the EU and elsewhere have published mandatory migration timelines for national security systems, explicitly citing Shor's algorithm as the threat driving the schedule, with target dates in the early-to-mid 2030s for full transition.

Cryptocurrency and blockchain. Bitcoin and Ethereum addresses derived from ECDSA public keys are directly vulnerable once exposed on-chain; this has spurred proposals for quantum-resistant signature schemes and address-rotation strategies within these ecosystems.

Long-term data confidentiality. Healthcare records, legal archives, and intelligence data with multi-decade confidentiality requirements are the most urgent migration priority, precisely because of the harvest-now-decrypt-later threat model.

Ask the tutor: How does the quantum Fourier transform actually extract the hidden period from the modular exponentiation function, step by step?