Shor's algorithm

A quantum algorithm, published by Peter Shor in 1994, that could factor large numbers and solve discrete logarithms quickly on a big enough quantum computer.

In more detail

Those two problems are what make RSA, Diffie-Hellman and elliptic curve cryptography hard to break, so Shor's algorithm would break all of them, along with the certificates and signatures built on them. Making the key bigger does not help much, because the algorithm's running time grows only slowly with key size. This threat is the reason post-quantum algorithms are being deployed now.

Example

Breaks: RSA, Diffie-Hellman, elliptic curves. Does not break: AES-256, SHA-256.

Related terms

Taught in

References