Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Discrete Logarithms & Elliptic Curves

Why ECC falls too, and with fewer qubits.

Elliptic-curve keys are about twelve times shorter than RSA keys of the same classical strength, because the best classical attacks on a good curve are generic. Shor's other algorithm ignores that distinction: it computes discrete logarithms in any group where you can compute, and its cost scales with the key length. Shorter keys mean a smaller quantum computer.

What you’ll learn

  • State the discrete logarithm problem, its cryptographic uses, and the classical attacks that set key sizes.
  • Derive Shor's discrete-log algorithm as Fourier sampling on Zr×Zr\Z_r\times\Z_r and recover ℓ\ell from one sample.
  • Explain what changes for elliptic curves (reversible point addition, unique representations) and why the logical-qubit count is lower than for RSA at equal security.
  • Describe short-discrete-log variants (Ekerå–Håstad) and which public-key systems survive.

The discrete logarithm problem

Generic algorithms, which only multiply and compare group elements, need Θ(r)\Theta(\sqrt r) operations: Pollard's rho method achieves this, and Shoup (1997) proved it optimal in the generic-group model. In Zp∗\Z_p^*, index calculus and the number field sieve exploit the arithmetic of integers and run in subexponential time, so pp must be thousands of bits long. For well-chosen elliptic curves no attack substantially better than generic is known, so a 256-bit curve already gives about 128-bit security.

Classical securityRSA modulus or finite-field ppElliptic-curve group order
128 bits3072 bits256 bits
192 bits7680 bits384 bits
256 bits15360 bits512 bits
Comparable key sizes, following NIST guidance.

Shor's discrete-log algorithm

Define f:Zr×Zr→Gf:\Z_r\times\Z_r\to G by f(a,b)=gahb=ga+ℓbf(a,b)=g^ah^b=g^{a+\ell b}. Then f(a,b)=f(a′,b′)f(a,b)=f(a',b') iff (a−a′)+ℓ(b−b′)≡0(modr)(a-a')+\ell(b-b')\equiv0\pmod r, so ff hides the subgroup H={(a,b):a+ℓb≡0}=⟨(−ℓ,1)⟩H=\{(a,b):a+\ell b\equiv0\}=\langle(-\ell,1)\rangle of order rr: a two-dimensional period-finding problem, solved by abelian Fourier sampling.

DerivationFourier sampling on Z_r × Z_r
  1. 1r∑a,b∈Zr∣a⟩∣b⟩∣gahb⟩\frac1r\sum_{a,b\in\Z_r}\ket a\ket b\ket{g^ah^b}

    Two uniform registers and one evaluation of ff, i.e. two exponentiations in GG.

  2. 1r∑b∈Zr∣k−ℓb⟩∣b⟩\frac{1}{\sqrt r}\sum_{b\in\Z_r}\ket{k-\ell b}\ket b

    Measuring the third register gives some gkg^k and leaves the coset {(k−ℓb,b)}\{(k-\ell b,b)\} of HH.

  3. (Fr⊗Fr): 1r3/2∑c,dωrck(∑bωrb(d−ℓc))∣c⟩∣d⟩=1r∑cωrck∣c⟩∣ℓc mod r⟩(F_r\otimes F_r):\ \frac{1}{r^{3/2}}\sum_{c,d}\omega_r^{ck}\Bigl(\sum_b\omega_r^{b(d-\ell c)}\Bigr)\ket c\ket d=\frac{1}{\sqrt r}\sum_{c}\omega_r^{ck}\ket c\ket{\ell c\bmod r}

    The sum over bb vanishes unless d≡ℓc(modr)d\equiv\ell c\pmod r: the outcome is uniform on H⊥={(c,ℓc)}H^\perp=\{(c,\ell c)\}.

  4. ℓ≡d c−1(modr)\ell\equiv d\,c^{-1}\pmod r

    If gcd⁡(c,r)=1\gcd(c,r)=1, a single sample determines ℓ\ell. For prime rr, the cryptographic case, this fails only when c=0c=0, with probability 1/r1/r.

Check your understanding

In the same group (r=10r=10, ℓ\ell unknown) you measure (c,d)=(7,9)(c,d)=(7,9). What is ℓ\ell?

  1. ℓ=3\ell=3
  2. ℓ=7\ell=7
  3. ℓ=9\ell=9
  4. ℓ=2\ell=2
Show the answer

B. ℓ=7\ell=7

7−1≡3(mod10)7^{-1}\equiv3\pmod{10} because 7⋅3=21≡17\cdot3=21\equiv1. So ℓ≡9⋅3=27≡7\ell\equiv9\cdot3=27\equiv7, consistent with d=ℓc=49≡9d=\ell c=49\equiv9.

If rr is not a power of two, FrF_r can be approximated efficiently (Kitaev 1995), or one uses registers of size 2q≈r2^q\approx r with Shor's original, slightly more involved post-processing; if rr is unknown, order finding supplies it. Boneh and Lipton (1995) extended the method to "black-box" groups, in which elements have unique encodings and the group operation is efficiently computable, covering both Zp∗\Z_p^* and elliptic curves.

Elliptic curves: same algorithm, different arithmetic

On an elliptic curve E:y2=x3+Ax+BE:y^2=x^3+Ax+B over Fp\mathbb F_p, the points form an abelian group under the chord-and-tangent law, with a large prime-order subgroup ⟨P⟩\langle P\rangle. The secret is ℓ\ell with Q=[ℓ]PQ=[\ell]P. Shor's circuit computes [a]P+[b]Q[a]P+[b]Q by double-and-add: the multiples [2i]P[2^i]P and [2i]Q[2^i]Q are classical constants, so the circuit is a sequence of about 2n2n controlled additions of a fixed point to a quantum point.

Predict before you look

Evaluate 9n+2⌈log⁡2n⌉+109n+2\lceil\log_2n\rceil+10 for a 256-bit curve such as P-256.

Show the answer

2330

9⋅256=23049\cdot256=2304, 2⌈log⁡2256⌉=162\lceil\log_2256\rceil=16, plus 10: 2330 logical qubits, compared with 2n+2=61462n+2=6146 for RSA-3072 with the circuits of Häner, Roetteler & Svore (2017).

Target (about 128-bit classical security)Key size nnLogical qubits (2017 circuits)
RSA-307230722n+2=61462n+2=6146
ECC P-25625623302330
Quantum cost grows with key length, so ECC's short keys, its classical strength, are its quantum weakness. Later optimizations cut the gate count further (Litinski 2023 reports about 50 million Toffolis for a 256-bit curve).

Short logarithms, tradeoffs and what survives

When the logarithm is known to be short, 0≤ℓ<2m0\le\ell<2^m with mm much smaller than log⁡2r\log_2r, Ekerå and Håstad (2017) showed how to size the exponent registers by mm rather than by log⁡2r\log_2r, with a tradeoff parameter ss: fewer qubits and gates per run in exchange for about ss runs combined by lattice-based post-processing. RSA fits this mold. For N=pqN=pq and a random gg, gN+1=gp+qg^{N+1}=g^{p+q} because g(p−1)(q−1)=1g^{(p-1)(q-1)}=1, so p+qp+q, an integer of about n/2n/2 bits, is a short discrete logarithm; pp and qq then follow from p+qp+q and pqpq by solving a quadratic. The Gidney–Ekerå RSA estimates use this formulation.

Shor's algorithms break every public-key system whose security reduces to factoring or to discrete logarithms in an abelian group: RSA, finite-field and elliptic-curve Diffie–Hellman, DSA, ECDSA. They do not apply to schemes built on lattices, codes, hash functions or multivariate equations, for which no polynomial-time quantum attacks are known; NIST standardized lattice-based ML-KEM and ML-DSA and hash-based SLH-DSA in 2024 (FIPS 203–205). Isogeny-based schemes sit in between: CSIDH rests on an abelian group action, which Kuperberg-type algorithms attack in subexponential time, while SIDH/SIKE fell in 2022 to a purely classical attack (Castryck & Decru), a reminder that post-quantum schemes must also be classically secure.

Key takeaways

  • Discrete logs: generic attacks need Θ(r)\Theta(\sqrt r) (Pollard rho, Shoup's lower bound), Zp∗\Z_p^* admits subexponential attacks, good curves only generic ones, so 256-bit ECC gives about 128-bit security.
  • Shor's algorithm: f(a,b)=gahbf(a,b)=g^ah^b hides ⟨(−ℓ,1)⟩\langle(-\ell,1)\rangle; Fourier sampling returns (c,ℓc)(c,\ell c), and ℓ=dc−1 mod r\ell=dc^{-1}\bmod r. It works in any black-box abelian group with unique encodings.
  • Elliptic curves need controlled additions of fixed points, affine coordinates and reversible inversion: 9n+2⌈log⁡2n⌉+10=23309n+2\lceil\log_2n\rceil+10=2330 logical qubits for n=256n=256, versus about 6100 for RSA-3072.
  • Short logarithms (Ekerå–Håstad) need registers sized by the logarithm's length; RSA factoring is a short discrete log of p+qp+q.
  • Lattice, code, hash and multivariate schemes survive (NIST FIPS 203–205, 2024); isogeny group actions face subexponential attacks, and SIDH fell classically.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

The function f(a,b)=gahbf(a,b)=g^ah^b with h=gℓh=g^\ell hides which subgroup of Zr×Zr\Z_r\times\Z_r?

  1. ⟨(ℓ,1)⟩\langle(\ell,1)\rangle
  2. ⟨(1,ℓ)⟩\langle(1,\ell)\rangle
  3. ⟨(−ℓ,1)⟩\langle(-\ell,1)\rangle
  4. The trivial subgroup {(0,0)}\{(0,0)\}
Show the answer

C. ⟨(−ℓ,1)⟩\langle(-\ell,1)\rangle

f(a,b)=ga+ℓbf(a,b)=g^{a+\ell b} is unchanged by adding (−ℓ,1)(-\ell,1): a+ℓba+\ell b shifts by −ℓ+ℓ=0-\ell+\ell=0. The level sets are exactly the cosets of ⟨(−ℓ,1)⟩\langle(-\ell,1)\rangle.

Question 2

Why does ECC-256 need fewer logical qubits to break than RSA-3072, although both give about 128-bit classical security?

  1. Shor's cost grows with key length, and ECC keys are short because only generic r\sqrt r classical attacks are known for good curves
  2. Elliptic-curve groups have smooth order
  3. ECC uses a non-abelian group, which is easier for Fourier sampling
  4. Point addition is cheaper than modular multiplication
Show the answer

A. Shor's cost grows with key length, and ECC keys are short because only generic r\sqrt r classical attacks are known for good curves

Roughly 9n9n logical qubits with n=256n=256 versus roughly 2n2n with n=3072n=3072. Each ECC operation is costlier, but the problem is twelve times smaller.

Question 3

Why do quantum elliptic-curve circuits use affine coordinates despite the cost of modular inversion?

  1. Because projective coordinates need more qubits per point
  2. Because inversion is cheap on a quantum computer
  3. Because Shor's algorithm only works over prime fields
  4. Because each point must have a unique encoding: with projective coordinates, equal points would differ across branches, ff would not be constant on cosets, and interference would be lost
Show the answer

D. Because each point must have a unique encoding: with projective coordinates, equal points would differ across branches, ff would not be constant on cosets, and interference would be lost

Classically, redundant representations are harmless. Quantumly, the register contents must depend only on the group element, otherwise the branches that should interfere carry different labels.

Question 4

Which scheme is, as far as is known, not broken by Shor's algorithms?

  1. ECDSA
  2. ML-KEM (lattice-based)
  3. Finite-field Diffie–Hellman
  4. RSA-OAEP
Show the answer

B. ML-KEM (lattice-based)

ML-KEM relies on module lattice problems, for which no efficient quantum algorithm is known. The other three reduce to factoring or abelian discrete logarithms.

Further reading

  • P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. Comput. 26, 1484 (1997); conference version in Proc. 35th IEEE FOCS (1994).
  • J. Proos & C. Zalka, "Shor's discrete logarithm quantum algorithm for elliptic curves", Quantum Inf. Comput. 3, 317 (2003).
  • M. Roetteler, M. Naehrig, K. M. Svore & K. Lauter, "Quantum resource estimates for computing elliptic curve discrete logarithms", ASIACRYPT 2017.
  • M. Ekerå & J. Håstad, "Quantum algorithms for computing short discrete logarithms and factoring RSA integers", PQCrypto 2017.
  • D. Boneh & R. J. Lipton, "Quantum cryptanalysis of hidden linear functions", CRYPTO '95.