# What is Shor’s algorithm?

Shor’s algorithm is a quantum method, described by Peter Shor in 1994, that factors large numbers and computes discrete logarithms in polynomial time. A large enough quantum computer running it would break RSA and elliptic-curve signatures such as ECDSA.

Also called Shor algorithm or Shor’s factoring algorithm.

## What it does

Factoring a large number into primes, and finding a discrete logarithm, are problems that classical computers solve with methods that become impractical as the numbers grow. Shor showed that a quantum computer can solve both in polynomial time, so the number of steps grows only as a polynomial in the size of the input.

## What it means for RSA and elliptic curves

- RSA rests in part on the difficulty of factoring the published number n, so Shor’s algorithm breaks RSA once a machine is large enough.
- Elliptic-curve signatures rest on the discrete logarithm problem on the curve, and Proos and Zalka described in 2003 how Shor’s method applies to it.
- NIST says that key exchange and signatures based on factoring and discrete logarithms, over finite fields and over elliptic curves, would be at risk if large-scale quantum computers are ever realized.

## What it means for ECDSA keys

An ECDSA key pair is a private number and a public point on the curve. A signature proves that the signer knows the private number, and anyone can check it against the public point. Shor’s algorithm recovers the private number from the public point, so a public key visible on the chain is exposed to any machine that can run the algorithm.

## In Redacted

In bunker mode, notes, proofs and signatures are built with no elliptic curves and no lattices, so the curve math that Shor’s algorithm breaks is not part of them.

More: [Bunker mode](https://redacted.gg/docs/using-redacted/bunker-mode.md)

## Related terms

- [Quantum computer](https://redacted.gg/glossary/quantum-computer.md): A quantum computer works with qubits, which can hold a combination of 0 and 1 and can be entangled with each other. A cryptographically relevant one would be large and reliable enough to break the public-key cryptography that wallets and websites rely on.
- [Elliptic curve cryptography](https://redacted.gg/glossary/elliptic-curve.md): Elliptic curve cryptography builds key pairs from points on an elliptic curve over a finite field. It gives about the strength of 3072-bit RSA with 256-bit keys, and Bitcoin signs with the secp256k1 curve.
- [ECDSA](https://redacted.gg/glossary/ecdsa.md): ECDSA is the elliptic-curve signature scheme behind most Bitcoin and Ethereum wallets. It proves that the holder of a private key approved a message without revealing the key, and its security rests on the secp256k1 curve.
- [Exposed public key](https://redacted.gg/glossary/exposed-public-key.md): A public key is exposed once it is visible on the chain, which usually happens the first time its address spends. Until then most addresses show only a hash of the key, which gives a key-breaking attacker nothing to start from.
- [Public-key cryptography](https://redacted.gg/glossary/public-key-cryptography.md): Public-key cryptography gives each person a private key that stays secret and a public key that anyone can see. A signature made with the private key can be checked with the public key, so no secret has to be shared in advance.
- [Post-quantum cryptography](https://redacted.gg/glossary/post-quantum-cryptography.md): Post-quantum cryptography is ordinary cryptography designed to stay secure when large quantum computers exist. It replaces the key exchanges and signatures that Shor’s algorithm breaks, such as RSA and elliptic curves, with schemes built on lattices, hash functions or error-correcting codes.

Sources: [Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter Shor, 1994](https://arxiv.org/abs/quant-ph/9508027), [Shor’s discrete logarithm quantum algorithm for elliptic curves, John Proos and Christof Zalka, 2003](https://arxiv.org/abs/quant-ph/0301141), [FIPS 204, Module-Lattice-Based Digital Signature Standard, NIST, 2024](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf)
---

Page: https://redacted.gg/glossary/shors-algorithm/