What Is Shor’s Algorithm?
Shor’s Algorithm is a quantum algorithm developed by Peter Shor in 1994. It solves the integer factorization problem and discrete logarithm problem exponentially faster than classical algorithms.
These problems are the foundation of cryptographic schemes like RSA and ECDSA. If we can solve them efficiently, we can derive private keys from public keys, thus breaking the security model of Bitcoin.
What Is the Goal?
Given a number NNN, find its prime factors.
For ECDSA (Bitcoin), the equivalent is solving the discrete logarithm problem:
Find xxx such that Q=xGQ = xGQ=xG, where:
- GGG is a generator point on an elliptic curve,
- QQQ is the public key,
- xxx is the private key (what Shor’s algorithm is trying to find).
Classical Problem:
To find the period rrr of the function: f(x)=axmod Nf(x) = a^x \mod Nf(x)=axmodN
This is classically hard because it takes exponential time as NNN grows.
Shor’s Algorithm Steps (Simplified)
- Choose a random integer aaa such that 1<a<N1 < a < N1<a<N and gcd(a,Na, Na,N) = 1.
- If gcd ≠ 1, you already found a factor.
- Use a quantum computer to find the period rrr of the function:
f(x)=axmod Nf(x) = a^x \mod Nf(x)=axmodN
- This uses the Quantum Fourier Transform (QFT) to efficiently identify the period.
- Once you have the period rrr:
- Check if rrr is even and ar/2≢−1mod Na^{r/2} \not\equiv -1 \mod Nar/2≡−1modN
- Then compute:
gcd(ar/2−1,N)andgcd(ar/2+1,N)\text{gcd}(a^{r/2} – 1, N) \quad \text{and} \quad \text{gcd}(a^{r/2} + 1, N)gcd(ar/2−1,N)andgcd(ar/2+1,N)
These will be non-trivial factors of NNN — i.e., you’ve factored it.
Why This Is Dangerous for Bitcoin
For ECDSA, the discrete logarithm problem on an elliptic curve is equivalent to factoring. Shor’s algorithm reduces this to polynomial time, potentially allowing a quantum computer to recover the private key xxx from the public key QQQ.
That’s why once you reuse a Bitcoin address, your public key is exposed — and if quantum computers become powerful enough, they can extract your private key.
Visual Representation of the Core Math
Let’s say: N=15,a=2N = 15, \quad a = 2N=15,a=2
We compute f(x)=2xmod 15f(x) = 2^x \mod 15f(x)=2xmod15
We get:
- 20=1mod 152^0 = 1 \mod 1520=1mod15
- 21=2mod 152^1 = 2 \mod 1521=2mod15
- 22=4mod 152^2 = 4 \mod 1522=4mod15
- 23=8mod 152^3 = 8 \mod 1523=8mod15
- 24=16=1mod 152^4 = 16 = 1 \mod 1524=16=1mod15
- Period r=4r = 4r=4
Then: gcd(2r/2−1,15)=gcd(4−1,15)=gcd(3,15)=3gcd(2r/2+1,15)=gcd(4+1,15)=gcd(5,15)=5\gcd(2^{r/2} – 1, 15) = \gcd(4 – 1, 15) = \gcd(3, 15) = 3 \gcd(2^{r/2} + 1, 15) = \gcd(4 + 1, 15) = \gcd(5, 15) = 5gcd(2r/2−1,15)=gcd(4−1,15)=gcd(3,15)=3gcd(2r/2+1,15)=gcd(4+1,15)=gcd(5,15)=5
So, we’ve factored 15 → {3, 5} using quantum methods.
In real cryptography, you’d replace 15 with a 300-digit number, and that’s what Shor’s algorithm can eventually break — with enough fault-tolerant qubits.
