Shor’s Algorithm: The Quantum Threat That Isn’t Here Yet — But Will Be

In 1994, mathematician Peter Shor proved that a quantum computer could factor large integers in polynomial time — effectively making RSA and elliptic-curve cryptography (ECC) obsolete. Classical computers would need billions of years to do what Shor’s Algorithm could do in hours.

The mechanism is elegant: it exploits quantum superposition and the quantum Fourier transform to find the period of a modular function, which directly yields the prime factors of a large number. The math is settled. The engineering is not.

Where are we today?

Google’s Willow chip operates at 105 physical qubits with improved coherence times (~100 microseconds) and better error correction architecture. Impressive — but running Shor’s at cryptographically relevant scales (2048-bit RSA, 256-bit ECC) requires:

• Thousands of logical (error-corrected) qubits

• Each logical qubit requiring potentially 1,000+ physical qubits for fault tolerance

• Deep circuits sustained over many gate operations without decoherence

That puts us at millions of physical qubits minimum. We have 105.

What should actually concern us now?

Not the attack itself, but the migration timeline. NIST has already standardized post-quantum algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium). Retrofitting global cryptographic infrastructure takes a decade. “Harvest now, decrypt later” attacks — where adversaries collect encrypted data today to decrypt once quantum hardware matures — are already a strategic concern for long-lived sensitive data.

The threat window is real. The threat itself is not imminent. Plan accordingly.