Skip to main content

> Term

Shor's Algorithm

A quantum algorithm discovered by Peter Shor in 1994 that solves prime factorization and discrete logarithms in polynomial time $O((\log N)^3)$, rendering classical RSA and ECC cryptography mathematically obsolete once CRQCs emerge.

Detailed Explanation

While classical computers require super-polynomial time to factor large semiprimes (the mathematical foundation of RSA), Shor's algorithm leverages quantum superposition and the Quantum Fourier Transform to compute periods in polynomial time, completely destroying public-key encryption.

Why It Matters

It is the foundational theoretical proof that classical public-key cryptography has an expiration date, driving the global mandate for Post-Quantum Cryptography.

Common Failure Mode

Assuming classical key size increases (e.g. RSA-4096 or ECC-521) defend against Shor's algorithm; they only add trivial extra quantum polynomial overhead.

Practical Example

A 4,096-qubit fault-tolerant quantum computer executing Shor's algorithm to recover the private key of an RSA-2048 certificate in seconds.

Production Manifestation

Adversaries execute Harvest Now, Decrypt Later (HNDL) programs in anticipation of executing Shor's algorithm on future hardware.

Frequently Asked Questions

What is Shor's Algorithm in short?

A quantum algorithm discovered by Peter Shor in 1994 that solves prime factorization and discrete logarithms in polynomial time $O((\log N)^3)$, rendering classical RSA and ECC cryptography mathematically obsolete once CRQCs emerge.

What is the most common failure mode?

Assuming classical key size increases (e.g. RSA-4096 or ECC-521) defend against Shor's algorithm; they only add trivial extra quantum polynomial overhead.

AI Summary

A quantum algorithm discovered by Peter Shor in 1994 that solves prime factorization and discrete logarithms in polynomial time $O((\log N)^3)$, rendering classical RSA and ECC cryptography mathematically obsolete once CRQCs emerge. It is the foundational theoretical proof that classical public-key cryptography has an expiration date, driving the global mandate for Post-Quantum Cryptography.