Shor’s Algorithm

Shor’s algorithm is a quantum algorithm developed by mathematician Peter Shor in 1994. Given a sufficiently powerful quantum computer, it can factor large integers and solve discrete logarithm problems, threatening the foundations of RSA and elliptic-curve cryptography. 

RSA, used for both encryption and signatures, is secured by how hard it is to break a large number down into the prime numbers that multiply together to make it. ECDSA (Elliptic Curve Digital Signature Algorithm), the signature scheme used to authorize most crypto transactions, relies on a different but equally hard mathematical problem involving points on an elliptic curve. 

Classical computers cannot solve either problem at cryptographic scale within any practical timeframe, and that difficulty is precisely what keeps private keys secure. Shor’s algorithm, run on a sufficiently capable quantum computer, would solve both problems efficiently, effectively dismantling that security guarantee.

How Shor’s Algorithm Works

The algorithm works in two phases. First, it uses a quantum technique called Quantum Phase Estimation to find a hidden repeating pattern in a mathematical function linked to the number being factored. Finding this pattern is the step that would take a classical computer an impractically long time 

Once the pattern is found, standard classical computation uses it to extract the prime factors. In practice, only very small numbers have been factored experimentally using Shor’s algorithm so far. Applying it to real cryptographic key sizes would require a quantum computer utilizing hardware that does not yet exist.

Why Shor’s Algorithm Matters For Crypto

Despite not being practically deployable today, Shor’s algorithm defines the threat model that post-quantum cryptography (PQC) is designed to address. On blockchains where spending funds reveals the public key associated with a spending address, a future quantum attacker running Shor’s algorithm could potentially derive the corresponding private key for schemes like ECDSA. 

The timeline for cryptographically relevant quantum computers remains uncertain, but the harvest now, decrypt later dynamic means that exposed public keys recorded today could become targets in the future. This is why NIST finalized its first post-quantum standards in 2024, including ML-DSA, intended as a post-quantum replacement for signature schemes such as ECDSA.