Quantum Computing &
Cryptanalysis

Shor's Algorithm and Public-Key Cryptography

RSA's security rests on the computational intractability of factoring the product of two large primes. The best known classical algorithm — the General Number Field Sieve — runs in sub-exponential time L_n[⅓, 1.923], making RSA-2048 infeasible to break with any foreseeable classical hardware. Shor's algorithm (1994) exploits quantum parallelism and the Quantum Fourier Transform to solve the period-finding problem in O((log N)³) time, reducing integer factorisation from sub-exponential to polynomial complexity.

The same algorithmic framework breaks the discrete logarithm problem (DLP), which underpins Diffie-Hellman key exchange and all elliptic curve cryptography (ECC). Since both factoring and DLP are instances of the Hidden Subgroup Problem over abelian groups, Shor's algorithm dispatches them with equal efficiency. A sufficiently large, fault-tolerant quantum computer would render RSA, DSA, ECDSA, ECDH, and EdDSA simultaneously and completely insecure.

Resource estimates: Early analyses estimated millions of physical qubits to break RSA-2048. A March 2025 paper by Bluvstein et al. demonstrated that advances in high-rate quantum error-correcting codes reduce this to as few as ~13,000 reconfigurable atomic qubits, with a runtime of days to weeks for RSA-2048 and potentially just days for ECC P-256 with ~12,000 qubits.

Grover's Algorithm and Symmetric Cryptography

Grover's algorithm (1996) provides a quadratic speedup for unstructured search: finding a marked item among N candidates in O(√N) queries instead of O(N). Applied to cryptographic key search, it effectively halves the security level of any symmetric cipher or hash function.

Practical impact: AES-128 drops to ~64-bit effective security — well within reach of a quantum adversary. AES-256 retains ~128 bits of effective security, which remains computationally infeasible. SHA-256 retains ~128-bit preimage resistance. The mitigation is straightforward: double key and hash lengths. No symmetric primitive is fundamentally broken.

Theoretical ceiling: Bennett, Bernstein, Brassard, and Vazirani proved that Grover's quadratic speedup is optimal — no quantum algorithm can do better for unstructured search. This means symmetric cryptography faces a bounded, well-characterised quantum threat, unlike the existential threat to asymmetric systems.

From Factoring to Period Finding

Step 1 — Classical reduction: Factoring N is reduced to finding the period r of the function f(x) = a^x mod N for a randomly chosen a coprime to N. If r is even and a^r/2 ≢ −1 (mod N), then gcd(a^r/2 ± 1, N) yields non-trivial factors.

Step 2 — Quantum period finding: Prepare a superposition over all x in {0, …, 2²ⁿ−1}, compute f(x) into an ancilla register, then apply the Quantum Fourier Transform (QFT) to the input register. Measurement yields a value close to a multiple of 2²ⁿ/r, from which r is extracted via the continued fractions algorithm.

Step 3 — Classical post-processing: Given r, compute gcd(a^r/2 ± 1, N) classically. If the result is trivial, repeat with a different random a. The probability of success per iteration is at least 1 − 1/2^k−1 where k is the number of distinct prime factors of N — typically succeeding in one or two attempts.

Key insight: The quantum advantage comes entirely from Step 2. Classically, period finding for f(x) = a^x mod N requires evaluating an exponential number of values. The QFT extracts the period from a quantum superposition of all function values simultaneously — this is the exponential speedup.

How Close Is the Threat?

The practical timeline for quantum cryptanalysis depends on three factors: qubit count, error rates, and gate speeds. As error correction improves, the physical qubit requirements drop rapidly — five orders of magnitude over two decades of research.