Quantum Discrete Logarithm Algorithm

The discrete logarithm problem is one of the two number-theoretic hinges — integer factoring is the other — on which almost all deployed public-key cryptography turns. Fix a finite cyclic group $G=\langle g\rangle$ of order $r$ , written multiplicatively, and an element $x\in G$ . Because $g$ generates the whole group, there is a unique exponent $s\in\{0,1,\dots,r-1\}$ with $x=g^{s}$ ; that exponent is the discrete logarithm $s=\log_g x$ . Classically it is believed hard: index calculus for the multiplicative group of a finite field runs in subexponential time, and the best generic methods — Pollard's rho, baby-step/giant-step — cost $\Theta(\sqrt r)$ , exponential in the bit-length $n=\log_2 r$ . Shor's discrete-log algorithm computes $s$ in time polynomial in $n$ , and with it every DLP-based scheme becomes breakable by a large fault-tolerant quantum computer. The trick is to make the unknown exponent geometric. Consider the two-variable function $f(a,b)=g^{a}x^{-b}=g^{\,a-sb}$ on $\mathbb{Z}_r\times\mathbb{Z}_r$ . Two inputs collide precisely when $a-sb\equiv a'-sb'\pmod r$ , that is, when their difference lies on the subgroup $H=\{(sb,b):b\in\mathbb{Z}_r\}$ — a one-dimensional line of slope $s$ inside the lattice $\mathbb{Z}_r^2$ . The hidden slope is the answer. Recovering a hidden subgroup of an abelian group from such a level-set-constant function is the abelian hidden subgroup problem, and the quantum Fourier transform diagonalises the coset structure so that a Fourier measurement exposes the subgroup, hence $s$ . Operationally the circuit builds a uniform superposition over $\mathbb{Z}_r^2$ , computes $f$ reversibly, discards that register to collapse onto one coset, and Fourier-transforms each index register; the measured outcomes then obey a linear congruence in $s$ , and a single good sample with the order $r$ yields $s$ by one modular division. The same machinery breaks Diffie–Hellman, DSA, ElGamal, and — most cheaply of all — elliptic-curve cryptography, which is why it drives the migration to post-quantum standards.

Key takeaways

The discrete logarithm problem asks: given a generator $g$ of a cyclic group of order $r$ and an element $x=g^{s}$ , find $s$ . Classically this is believed exponentially hard; quantumly Shor solves it in time polynomial in $\log r$ .
The engine reframes DLP as a hidden-subgroup problem: the function $f(a,b)=g^{a}x^{-b}$ is constant exactly on cosets of the line $H=\{(sb,b)\}\le\mathbb{Z}_r^2$ , so the unknown exponent is a hidden slope.
Two quantum Fourier transforms over $\mathbb{Z}_r$ send that slope to a measured congruence $c_2+s\,c_1\equiv0\pmod r$ ; one modular division $s\equiv-c_2 c_1^{-1}$ then recovers the logarithm.
The group order $r$ is supplied first by order finding — the period-finding core of Shor's factoring algorithm — or is simply read off when the group has publicly known prime order.
Each shot succeeds with probability $\varphi(r)/r$ , which is $(r-1)/r\to1$ for the prime-order groups used in cryptography, so a handful of repetitions suffice.
ECC is the most fragile target: a 256-bit elliptic curve falls to a few thousand logical qubits, fewer than RSA-2048, because its group order is smaller.
Key idea: encode the unknown exponent as the slope of a hidden line $H=\{(sb,b)\}\le\mathbb{Z}_r^2$ through $f(a,b)=g^{a}x^{-b}$ ; a double quantum Fourier transform over $\mathbb{Z}_r$ turns that slope into a measured linear constraint $c_2+s\,c_1\equiv0\,(\mathrm{mod}\,r)$ , and modular division recovers $s$ .

The core insight

Encode the unknown exponent as the slope of a hidden line $H=\{(sb,b)\}\le\mathbb{Z}_r^2$ through the function $f(a,b)=g^{a}x^{-b}$ ; a double quantum Fourier transform over $\mathbb{Z}_r$ turns that slope into a measured linear constraint $c_2+s\,c_1\equiv0\,(\mathrm{mod}\,r)$ , from which one modular division recovers $s$ .

Where this lives today

No machine can yet run the discrete-log algorithm at cryptographically relevant sizes — the largest honest demonstrations involve a handful of qubits on toy groups, orders of magnitude short of the thousands of high-fidelity logical qubits and billions of Toffoli gates the resource estimates demand. Yet the algorithm dominates present-day cryptographic planning because of the "harvest now, decrypt later" threat: an adversary can record encrypted traffic today and decrypt it the day a capable machine exists, so any secret that must stay confidential for a decade is already at risk. That logic drove the US National Institute of Standards and Technology to finalise in 2024 the lattice-based standards ML-KEM (FIPS 203), ML-DSA (FIPS 204), and SLH-DSA (FIPS 205) as replacements for Diffie–Hellman, DSA, and ECDSA. Refined resource studies — Roetteler and colleagues for elliptic curves, Gidney and Ekerå for RSA — confirm that ECC, with its smaller group order, is the cheapest target. And the same abelian-hidden-subgroup lens that makes DLP easy sharpens the frontier of what remains hard: the non-abelian hidden subgroup problems behind graph isomorphism and, most consequentially, the lattice problems on which the new standards rest, for which no analogous quantum Fourier attack is known.

The physical picture

Think of multiplication-by- $g$ as walking around a ring of $r$ stations; computing $\log_g x$ asks "how many steps $s$ land you on $x$ ?". Classically you essentially have to walk the ring, because the ordering of powers carries no exploitable structure. Quantumly you instead build a function whose repeating pattern is the answer: $f(a,b)=g^{a}x^{-b}=g^{a-sb}$ takes the same value whenever you move along the direction $(s,1)$ , so $s$ is baked into the geometry of where $f$ repeats — and the Fourier transform reads geometry as frequency. The two index registers behave like a two-dimensional grating: after you compute and discard $f$ , the surviving amplitude lives on a single tilted coset, and transforming a line of slope $s$ produces a dual line of slope $-s$ in frequency space, so each measurement samples one point of that dual line — a clean linear equation in the unknown.

Figure

Index space and frequency space for the toy instance g = 3, x = 5 in the order-5 subgroup modulo 11, so s = 3. Left: the 25 points of ℤ₅ × ℤ₅; discarding the oracle register collapses the state onto one coset of the hidden line H = the points (3b, b), shown in blue, with a neighbouring coset in amber. Right: the double Fourier transform makes every measurement land on the dual line c₂ + 3 c₁ ≡ 0 mod 5, the five green points, and any one of them gives an equation that recovers s

Why does one equation suffice, when a classical solver would need to walk the whole ring? Because the quantum machine also hands you the modulus $r$ , and a single congruence $c_2\equiv-s\,c_1\pmod r$ pins $s$ uniquely as soon as $c_1$ is invertible — which a random $c_1$ is with probability $\varphi(r)/r$ , equal to $(r-1)/r$ for the prime-order groups cryptographers deploy. The whole construction is the abelian hidden subgroup problem in a cryptographic costume: Shor's factoring hides a period $\mathbb{Z}_r\le\mathbb{Z}$ , discrete log hides a slope $\{(sb,b)\}\le\mathbb{Z}_r^2$ ; same Fourier engine, different hidden subgroup. The circuit is short — prepare, oracle, discard, transform, measure — and the only expensive part is realising group multiplication as a reversible arithmetic circuit.

Figure

The discrete-logarithm circuit. Two index registers over ℤ_r are placed in a uniform superposition by a Fourier or Hadamard prep F_r, the oracle writes f = gᵃ x⁻ᵇ into a third register, that register is measured and discarded to collapse the state onto one coset, a quantum Fourier transform over ℤ_r is applied to each index register, and the final measurement returns a pair c₁ and c₂ obeying c₂ + s c₁ ≡ 0 mod r, from which s follows by one modular division

The core equations

The problem itself is one line: a target element is a known power of the generator, and the exponent is what we want. Everything the algorithm does is a way to read that exponent out of the group's structure rather than by search.

x=g^{s},\qquad s=\log_g x\in\{0,1,\dots,r-1\} \qquad (1)

where: $g$ — generator of a finite cyclic group $G$ ; $r$ — the group order, $r=|G|$ , so $g^{r}=e$ ; $x$ — the target element; $s$ — the unknown exponent, the discrete logarithm. Reading it: because $g$ generates $G$ , the map $s\mapsto g^{s}$ is a bijection $\mathbb{Z}_r\to G$ , so $s$ exists and is unique — the difficulty is purely computational. The single design decision that makes the problem tractable is the two-variable function below. It combines a power of the generator with an inverse power of the target so that the answer $s$ enters as the coefficient tying the two indices together.

f(a,b)=g^{a}x^{-b}=g^{\,a-sb},\qquad (a,b)\in\mathbb{Z}_r\times\mathbb{Z}_r \qquad (2)

where: $a,b$ — index variables ranging over $\mathbb{Z}_r$ ; $f(a,b)$ — a group element depending only on the combination $a-sb\bmod r$ ; $x^{-b}=g^{-sb}$ — the source of the $-sb$ term. Reading it: $f$ can only "see" the linear form $a-sb$ , so its level sets are the lines of slope $s$ — collisions occur exactly along the hidden subgroup $H=\{(sb,b):b\in\mathbb{Z}_r\}\le\mathbb{Z}_r^2$ , and learning that slope is solving DLP (the derivation below makes this precise). Running the oracle on the uniform superposition entangles every input pair with its function value in a third register, so all $r^{2}$ evaluations coexist.

|\psi_0\rangle=\frac{1}{r}\sum_{a=0}^{r-1}\sum_{b=0}^{r-1}|a\rangle|b\rangle|f(a,b)\rangle \qquad (3)

where: $|a\rangle|b\rangle$ — two index registers, each uniform over $\mathbb{Z}_r$ ; $|f(a,b)\rangle$ — the function register holding $g^{a-sb}$ via reversible group arithmetic; $1/r$ — normalisation of the $r^{2}$ equal terms. Reading it: this is quantum parallelism, but by itself it is useless — the point is what interference does next. Measuring (or simply discarding) the function register collapses the state onto the inputs sharing one value of $f$ — a single coset of the hidden line, with an unknown offset $a_0$ .

|\psi_1\rangle=\frac{1}{\sqrt r}\sum_{b=0}^{r-1}|\,sb+a_0\,\rangle\,|b\rangle \qquad (4)

where: $a_0$ — the value with $g^{a_0}$ equal to the measured $f$ -outcome; $sb+a_0$ — the first-register index, locked to the line of slope $s$ mod $r$ . Reading it: the slope $s$ now lives in the correlation between the registers, not in any single amplitude, and the offset $a_0$ is about to become harmless. The transform that reads slope as frequency is the quantum Fourier transform over $\mathbb{Z}_r$ — the abelian character sum. Applied to each index register it maps the tilted coset onto its dual line.

\mathrm{QFT}_r:\ |y\rangle\ \mapsto\ \frac{1}{\sqrt r}\sum_{c=0}^{r-1}e^{\,2\pi i\,yc/r}\,|c\rangle \qquad (5)

where: $y$ — input index in $\mathbb{Z}_r$ ; $c$ — the conjugate (frequency) index; $e^{2\pi i yc/r}$ — the character of $\mathbb{Z}_r$ at $(y,c)$ . Reading it: characters are orthogonal, so a complete phase sum either reinforces to $r$ or cancels to $0$ — the mechanism that carves out the dual line. After the double transform the probability is supported only on outcomes satisfying a linear congruence; the unknown offset $a_0$ has dropped out as a pure phase.

\Pr[(c_1,c_2)]=\begin{cases}\dfrac1r,& c_2+s\,c_1\equiv 0\ (\mathrm{mod}\ r)\\[4pt]0,&\text{otherwise}\end{cases} \qquad (6)

where: $c_1,c_2$ — measured frequencies of the two index registers; $c_2+s\,c_1\equiv0$ — the dual-line constraint carrying $s$ ; $1/r$ — uniform weight over the $r$ allowed points. Reading it: every shot returns one point of the dual line, i.e. one linear equation in the single unknown $s$ . One equation with an invertible coefficient determines $s$ by a modular division — the extended Euclidean algorithm supplies the inverse in polynomial time.

s\equiv-\,c_2\,c_1^{-1}\ (\mathrm{mod}\ r),\qquad \gcd(c_1,r)=1 \qquad (7)

where: $c_1^{-1}$ — the inverse of $c_1$ in $\mathbb{Z}_r$ ; $\gcd(c_1,r)=1$ — the invertibility condition. Reading it: whenever the sampled $c_1$ is coprime to $r$ the logarithm falls out in one step, and the candidate is checked for free by recomputing $g^{s}\stackrel{?}{=}x$ . The chance that a shot is usable is the fraction of invertible residues — the Euler totient ratio — which is near one for prime order.

\Pr[\gcd(c_1,r)=1]=\frac{\varphi(r)}{r}\ \xrightarrow{\ r\ \text{prime}\ }\ \frac{r-1}{r} \qquad (8)

where: $\varphi(r)$ — Euler's totient, the count of residues coprime to $r$ ; $(r-1)/r$ — the prime-order limit. Reading it: for the prime-order groups of real cryptosystems essentially every shot works, so a constant number of repetitions gives certainty.

Derivation AWhy the oracle hides the logarithm as a slope

The goal is to prove that the function $f(a,b)=g^{a}x^{-b}$ is constant exactly on the cosets of the line $H=\{(sb,b)\}$ , so that "find the hidden subgroup of $\mathbb{Z}_r^2$ on which $f$ is invariant" is literally the same problem as "find the discrete logarithm $s$ " — the structural claim that converts an unstructured search into a hidden-subgroup problem an abelian Fourier transform can crack. We start from the collision condition and read off the subgroup.

Step 1. Write out when two inputs agree: $f(a,b)=f(a',b')$ means $g^{a-sb}=g^{a'-sb'}$ , and since $g$ has order $r$ , equal powers force equal exponents mod $r$ , i.e. $a-sb\equiv a'-sb'\pmod r$ . Why: the order of the generator is what turns an equality of group elements into a linear congruence — the only place the group structure enters.

Step 2. Rearrange the congruence into a statement about the difference of inputs: $(a-a')\equiv s\,(b-b')\pmod r$ . Setting $\Delta=(a-a',\,b-b')$ , this says $\Delta$ lies on the line of slope $s$ through the origin. Why: collisions are governed only by input differences, so the invariance structure is a subgroup, not a scattered set.

Step 3. Collect all such differences into $H=\{(sb,b):b\in\mathbb{Z}_r\}$ and check it is a subgroup: it is closed under addition mod $r$ , contains $(0,0)$ , and has order $r$ because $b$ ranges over $\mathbb{Z}_r$ . Thus $f(a,b)=f(a',b')$ iff $(a,b)-(a',b')\in H$ . Why: this is exactly the defining property of a hidden subgroup — $f$ is constant on cosets of $H$ and distinct across them.

Step 4. Read off the payload: the slope of $H$ is $s$ , so any procedure that identifies the hidden subgroup returns the discrete logarithm. A concrete check ( $g=3$ , $x=5$ , $r=5$ , so $s=3$ ) gives $H=\{(0,0),(3,1),(1,2),(4,3),(2,4)\}$ , the blue points of the first figure. Why: it grounds the abstract subgroup in the numeric instance we will carry through the worked example, confirming the slope really equals the answer. *Note: direct enumeration for the $r=5$ instance confirms $f$ is constant on every coset of $H=\{(sb,b)\}$ ; the subgroup axioms hold because $\{(s,1)\}$ generates a cyclic group of order $r$ in $\mathbb{Z}_r^2$ .*

Go deeper · Derivation B · 2 minFourier sampling pins the slope

Derivation BFourier sampling pins the slope

The goal is to carry the post-measurement coset state through the two quantum Fourier transforms and show that amplitude survives only on the dual line $c_2+s\,c_1\equiv0\pmod r$ , with the unknown coset offset $a_0$ demoted to an unobservable phase. This is the heart of the algorithm — where the geometry of the hidden slope is converted, by the orthogonality of characters, into a measurement yielding a clean linear equation in the single unknown $s$ . We transform each register in turn and collapse the resulting phase sum.

Step 1. Transform the first register. Each index $sb+a_0$ maps under $\mathrm{QFT}_r$ to $\tfrac{1}{\sqrt r}\sum_{c_1}e^{2\pi i(sb+a_0)c_1/r}|c_1\rangle$ . Why: the first register carries the slope information as the coefficient of $b$ inside the phase, which is what the transform will expose.

Step 2. Transform the second register. The index $b$ maps to $\tfrac{1}{\sqrt r}\sum_{c_2}e^{2\pi i bc_2/r}|c_2\rangle$ , a standard $\mathrm{QFT}_r$ . Why: applying the transform to both registers is what builds the two-dimensional dual pattern rather than a one-dimensional spectrum.

Step 3. Collect the sum over $b$ . The amplitude of $|c_1\rangle|c_2\rangle$ is $\tfrac{e^{2\pi i a_0 c_1/r}}{r^{3/2}}\sum_{b=0}^{r-1}e^{2\pi i b(s c_1+c_2)/r}$ , and the inner sum is a complete geometric series equal to $r$ when $s c_1+c_2\equiv0\pmod r$ and $0$ otherwise. Why: this is character orthogonality on $\mathbb{Z}_r$ , $\sum_b e^{2\pi i bk/r}=r\,\delta_{k\equiv0}$ — the exact cancellation that carves the dual line out of the full grid.

Step 4. Read off the amplitude and probability. On the surviving line the amplitude is $\tfrac{1}{\sqrt r}\,e^{2\pi i a_0 c_1/r}$ , so $\Pr[(c_1,c_2)]=\tfrac1r$ for $c_2+s c_1\equiv0$ and $0$ elsewhere. The offset $a_0$ appears only in the modulus-one phase $e^{2\pi i a_0 c_1/r}$ and cancels in $|\cdot|^2$ . Why: this is precisely why discarding the function register — which fixed $a_0$ to an unknown value — costs nothing: the offset never reaches the probabilities.

Step 5. Confirm normalisation and the geometry. There are exactly $r$ allowed pairs (one $c_2$ for each $c_1$ ), each with weight $1/r$ , summing to $1$ ; the allowed set is the dual line of slope $-s$ . For the $r=5,\,s=3$ instance the outcomes are $(0,0),(1,2),(2,4),(3,1),(4,3)$ — the green points of the first figure, each with probability $0.2$ . Why: the numeric check confirms both the constraint and the uniform-over-the-line distribution the next derivation exploits. *Note: direct simulation of the double $\mathrm{QFT}_5$ on the coset state reproduces the five outcomes at probability $0.2$ each, all satisfying $c_2+3c_1\equiv0\pmod5$ .*

Go deeper · Derivation C · 1 minRecovering s and the totient success bound

Derivation CRecovering s and the totient success bound

The goal is to show that one Fourier sample with an invertible coordinate determines $s$ exactly by a single modular division, and to compute the per-shot success probability as the totient ratio $\varphi(r)/r$ , near one for prime order. This closes the loop from measurement to answer and quantifies how many repetitions the algorithm needs. We invert the sampled congruence, count the good samples, and bound the failure of repetition.

Step 1. Start from a measured pair obeying $c_2+s\,c_1\equiv0\pmod r$ . Solving for $s$ gives $s\equiv-c_2\,c_1^{-1}\pmod r$ , provided $c_1^{-1}$ exists. Why: the whole informational content of a shot is this one linear equation, and division is the only step needed to expose $s$ .

Step 2. Determine when the inverse exists: $c_1^{-1}$ is defined iff $\gcd(c_1,r)=1$ , and the extended Euclidean algorithm returns it in $O((\log r)^2)$ bit operations. Why: a non-invertible $c_1$ (in particular $c_1=0$ ) yields a congruence that does not isolate $s$ — the sample is discarded, not wrong.

Step 3. Count the usable samples. Because the $r$ outcomes are uniform, the probability that $c_1$ is invertible equals the fraction of residues coprime to $r$ , which is $\varphi(r)/r$ by definition of the totient. Why: this converts the algebra of invertibility directly into the success probability of a single run.

Step 4. Specialise to cryptographic groups. When $r$ is prime every nonzero residue is invertible, so $\varphi(r)/r=(r-1)/r\to1$ : essentially every shot succeeds. Any candidate is verified for free by testing $g^{s}=x$ , removing residual ambiguity. Why: real DLP groups use prime order precisely so that one shot almost always suffices and verification is trivial.

Step 5. Bound repetition for the worst case. Even for composite $r$ where $\varphi(r)/r$ dips, the failure probability after $k$ independent shots is at most $(1-\varphi(r)/r)^{k}$ , which decays exponentially, so $O(\log\log r)$ runs drive it below any threshold. Why: it guarantees efficiency uniformly, since $\varphi(r)/r=\Omega(1/\log\log r)$ is the worst the totient ratio can be. *Note: for the $r=5$ instance each invertible sample $(1,2),(2,4),(3,1),(4,3)$ returns $s=3$ by $s\equiv-c_2 c_1^{-1}\bmod5$ , and $\varphi(5)/5=0.8$ matches the prime limit $(r-1)/r$ .*

Limiting cases

The cost of discrete log depends sharply on the group, the algorithm, and whether you are the attacker or the defender:

Case	Result	Meaning
Classical generic DLP	$T_{\mathrm{cl}}=\Theta(\sqrt r)$	Pollard rho and baby-step/giant-step in a black-box group of order $r$ take $\Theta(\sqrt r)\approx2^{n/2}$ steps — exponential in the bit-length $n=\log_2 r$ , and provably optimal in the generic-group model.
Quantum (Shor) DLP	$T_{\mathrm{q}}=O\!\big((\log r)^2\log\log r\big)$	Polynomially many group multiplications and QFTs in the input size $n$ ; the dominant cost is reversible modular exponentiation or scalar multiplication.
ECDLP qubit count	$N_{\mathrm{qubits}}\approx 6n+O(\log n)$	For an elliptic curve over an $n$ -bit field the Proos–Zalka estimate is of order $6n$ logical qubits; a 256-bit curve needs a few thousand, fewer than RSA-2048.
Symmetric-key contrast	$T_{\mathrm{Grover}}=\Theta(2^{k/2})$	Public-key DLP collapses to polynomial time, but Grover only halves the effective key length of a $k$ -bit symmetric cipher — so AES-256 keeps $2^{128}$ security.
Prime vs composite order	$\Pr_{\text{shot}}=\varphi(r)/r$	Prime order gives near-certain success per shot; composite order lowers the totient ratio, costing a few extra repetitions but no change in asymptotic efficiency.

Common trapThe Fourier transform can be over any convenient power of two

It cannot, not without extra work. The transform that produces the clean congruence $c_2+s\,c_1\equiv0$ is $\mathrm{QFT}_r$ over the true group order $r$ . If you substitute $\mathrm{QFT}_{2^m}$ for a convenient power of two with $r\nmid 2^m$ , the character sums no longer cancel exactly: spectral leakage smears the outcomes so they only approximately satisfy the constraint, and a naive modular division then returns the wrong $s$ . Two things must be added back. First, you must actually know $r$ — supplied by the order-finding subroutine (the period-finding core of Shor's factoring algorithm) unless the group has publicly known order. Second, you must post-process the approximate outcomes exactly as in phase estimation, using continued fractions or lattice rounding to snap $c/2^m$ back to the nearest $j/r$ . Skip either the order-finding or the continued-fraction step and the recovered logarithm is simply incorrect. The exact- $\mathrm{QFT}_r$ presentation hides this because it assumes $r$ is already in hand.

Worked examples

1 · Solving a discrete log end to end (fully worked)

Work in the order-5 subgroup of $\mathbb{Z}_{11}^{\ast}$ generated by $g=3$ , with target $x=5$ . Find $s=\log_3 5$ by running the algorithm and recovering $s$ from a single Fourier sample.

Step 1. Fix the group and check the order. The powers of $g=3$ mod $11$ are $3^0=1,\ 3^1=3,\ 3^2=9,\ 3^3=5,\ 3^4=4,\ 3^5=1$ , so $G=\{1,3,9,5,4\}$ has prime order $\mathbf{r=5}$ . The target $x=5$ sits in $G$ , so a logarithm exists; the answer we are hunting is the $s$ with $3^{s}=5$ .

Step 2. Form the oracle function and its hidden line. The circuit evaluates $f(a,b)=3^{a}\cdot5^{-b}=3^{a-sb}\pmod{11}$ over $(a,b)\in\mathbb{Z}_5^2$ . Its hidden subgroup is $H=\{(sb,b)\}$ ; with the true $s=3$ this is $\mathbf{H=\{(0,0),(3,1),(1,2),(4,3),(2,4)\}}$ — the blue coset in the first figure. The algorithm does not know $s$ yet; it only prepares the superposition and calls $f$ once.

Step 3. Discard the function register and Fourier-sample. Measuring $f$ collapses the state onto one coset of $H$ ; the double $\mathrm{QFT}_5$ then spreads all probability onto the dual line $c_2+3c_1\equiv0\pmod5$ . The five equally likely outcomes are $\mathbf{(0,0),(1,2),(2,4),(3,1),(4,3)}$ , each with probability $0.2$ — exactly the green points of the figure and the simulation.

Step 4. Recover $s$ from one good sample. Suppose the measurement returns $(c_1,c_2)=(1,2)$ . Since $\gcd(c_1,5)=1$ , invert: $c_1^{-1}=1^{-1}=1$ , so $s\equiv-c_2 c_1^{-1}=-2\cdot1\equiv\mathbf{3}\pmod5$ . Cross-check with a different shot $(2,4)$ : $2^{-1}=3$ in $\mathbb{Z}_5$ , so $s\equiv-4\cdot3=-12\equiv3$ . Both agree.

Step 5. Verify and interpret. Confirm the candidate directly: $3^{3}=27\equiv5\pmod{11}=x$ . So $\log_3 5=3$ , obtained from a single oracle call plus one modular division; the only useless outcome is $(0,0)$ , where $c_1=0$ is not invertible, occurring with probability $1/5$ .

2 · Why elliptic curves fall first (resource scaling)

Compare the quantum cost of breaking a 256-bit elliptic curve with breaking RSA-2048, and contrast both with the classical effort.

Step 1. Classical baseline. The best generic attack on a 256-bit curve is Pollard rho at $\Theta(\sqrt r)\approx2^{128}$ group operations — beyond any classical machine, which is why 256-bit ECC is standardised for 128-bit security. Shor's algorithm ignores this, costing only $O(n^2\log n)$ -scale reversible operations in $n=256$ .

Step 2. Logical-qubit count. Proos–Zalka scaling gives $N\approx6n$ logical qubits, so $6\times256\approx\mathbf{1500}$ ; careful modern synthesis (Roetteler and collaborators) lands near $\mathbf{2300}$ once ancillas for reversible field arithmetic are counted. RSA-2048 by contrast needs $\approx2n\approx\mathbf{4100}$ logical qubits, its modulus being eight times longer than the curve's field.

Step 3. Read the asymmetry. The break cost scales with the bit-length of the group order, and ECC deliberately uses a small order for a given security level — its whole classical selling point. Against a quantum computer that economy inverts into fragility: a 256-bit curve needs about half the logical qubits of RSA-2048, making ECDLP arguably the first public-key primitive a fault-tolerant machine would break.

3 · Composite order and repetitions

The group has composite order $r=15$ . How many shots for 99% confidence?

Step 1. Totient ratio. The residues coprime to $15$ are $\{1,2,4,7,8,11,13,14\}$ , so $\varphi(15)=8$ and each shot succeeds with probability $\varphi(15)/15=\mathbf{8/15\approx0.53}$ — barely better than a coin, because $15=3\times5$ has many zero divisors.

Step 2. Repetition bound. Failure after $k$ shots is at most $0.47^{k}$ , and $0.47^{k}\le0.01$ needs $k\approx7$ . Composite order costs only a small constant factor; prime-order groups, with $\varphi(r)/r=(r-1)/r$ , essentially never need more than one shot.

Physics of the portrait

Discrete log and factoring were sister hardness assumptions for two decades before one paper showed a quantum computer dissolves both at once. That paper, and the algorithm carried through this article, belong to Peter Shor.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

born 1959, New York City · the quantum algorithms that break RSA, Diffie–Hellman, and elliptic-curve cryptography

Peter Williston Shor is the mathematician who turned quantum computing from an intriguing model into a threat and a discipline. Working at Bell Labs in the early 1990s, he was struck by Daniel Simon's 1994 result that a quantum computer could find a hidden period with an exponential advantage that survives bounded error. Shor saw that the same Fourier-sampling idea, carried from the group $\mathbb{Z}_2^n$ to $\mathbb{Z}_N$ , would expose the period of modular exponentiation — and therefore factor integers and, by the slope construction of this article, compute discrete logarithms. His 1994 conference paper carried both in its title, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", with the full analysis appearing in the SIAM Journal on Computing in 1997. The impact was immediate and double-edged: it promised that a scalable quantum computer would break RSA, Diffie–Hellman, DSA, ElGamal, and elliptic-curve cryptography, and it made the theory of quantum algorithms suddenly consequential. Shor did not stop there — in 1995 he introduced the first quantum error-correcting code, the nine-qubit code showing fault-tolerant quantum computation was possible in principle and removing the most serious objection to his own algorithm's feasibility. Now a professor at MIT, his work has been recognised with the Nevanlinna Prize, the Gödel Prize, the Dirac Medal, and the 2023 Breakthrough Prize in Fundamental Physics. The discrete-logarithm algorithm and its factoring sibling remain the reason the world is now rebuilding its cryptographic foundations.

History

1976

— Diffie and Hellman found public-key cryptography on the hardness of discrete logarithms

1985

— ElGamal builds encryption and signatures on the DLP, and Koblitz and Miller propose elliptic-curve cryptography

1994

— Shor announces polynomial-time quantum algorithms for factoring and discrete logarithms

1997

— the full analysis appears in the SIAM Journal on Computing

2003

— Proos and Zalka work out the elliptic-curve discrete-log qubit cost

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, §5.4 (order finding, factoring, and the discrete-log discussion) · Preskill, Lecture Notes for Physics 219, Ch. 6 (abelian Fourier sampling and discrete log) · Kitaev, Shen and Vyalyi, Classical and Quantum Computation, §13 (the abelian stabiliser and hidden subgroup problems) · Watrous, quantum-algorithms and hidden-subgroup lecture notes · Mermin, Quantum Computer Science, Ch. 3 (period finding and its applications).

Primary and resource sources. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput. 26, 1484 (1997) · Proos and Zalka, Shor's discrete logarithm quantum algorithm for elliptic curves, Quantum Inf. Comput. 3, 317 (2003) · Roetteler, Naehrig, Svore and Lauter, Quantum resource estimates for computing elliptic curve discrete logarithms, ASIACRYPT 2017 · Gidney and Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021). The key checkpoints of this article are: (1) $f(a,b)=g^{a}x^{-b}$ is constant exactly on cosets of $H=\{(sb,b)\}\le\mathbb{Z}_r^2$ ; (2) the character-orthogonality sum $\sum_{b=0}^{r-1}e^{2\pi i bk/r}=r\,\delta_{k\equiv0\,(r)}$ yields the dual-line constraint $c_2+s c_1\equiv0$ ; (3) the toy instance $g=3$ , $x=5$ , $r=5$ , $s=3$ gives outcomes $(0,0),(1,2),(2,4),(3,1),(4,3)$ at probability $0.2$ each, with $s\equiv-c_2 c_1^{-1}\equiv3\pmod5$ from every invertible sample; (4) the per-shot success probability is $\varphi(r)/r$ , with prime limit $(r-1)/r$ and $\varphi(15)/15=8/15$ ; (5) the ECDLP logical-qubit cost is $\approx6n$ against $\approx2n$ for RSA.

Prerequisites. Quantum Fourier Transform · Order Finding and Period Finding · Hidden Subgroup Problem · Quantum Phase Estimation · Shor's Factoring Algorithm. Leads to. Hidden Subgroup Problem · Post-Quantum Cryptography · Grover's Search Algorithm.

Ask the tutor: Ask me to run the algorithm on any small group you choose — pick a generator, a target, and an order, and watch the hidden slope turn into a measured line and then into the recovered logarithm.

Why does discarding the function register before the Fourier transform not throw away s?

Because the slope lives in the correlation between the two index registers, not in any single amplitude. Measuring $f$ collapses the state onto one coset $\{(sb+a_0,\,b)\}$ of the hidden line, where the only thing lost is the coset label $a_0$ — the specific value of the discarded function output. That $a_0$ enters the post-transform amplitude solely through the phase factor $e^{2\pi i a_0 c_1/r}$ , which has modulus one and cancels when you take $|\text{amplitude}|^2$ . So the measurement probabilities depend only on $s$ , never on which coset you happened to land in. This is why the algorithm can afford to throw the function register away rather than uncompute it: the offset it fixes is invisible to the final statistics.

How can a single measured equation determine s, when classically you would need to search?

The single congruence $c_2+s\,c_1\equiv0\pmod r$ has one unknown, $s$ , and one modulus, $r$ . As soon as $c_1$ is invertible mod $r$ you divide once, $s\equiv-c_2 c_1^{-1}$ , and $s$ is pinned exactly — there is nothing left to search. The reason this works quantumly and not classically is that the equation is handed to you already true: the Fourier interference guarantees every measured pair lies on the dual line, so the sample is not a guess to be tested but a constraint to be solved. Classically you have no way to produce such a constraint without effectively walking the group. Knowing $r$ is essential to the division, which is why order finding runs first when the order is not already public.

What exactly does the order-finding subroutine contribute, and when is it unnecessary?

The discrete-log step transforms over $\mathbb{Z}_r$ and finishes with a division mod $r$ , so the order $r$ must be known before you start. Order finding — the period-finding heart of Shor's factoring algorithm — supplies it: it samples $c/2^m\approx j/r$ from a periodic function $h(m)=g^{m}$ and extracts $r$ by continued fractions once $2^m\ge r^2$ . That subroutine is only needed when the order is genuinely unknown. For the standardised cryptographic groups that matter in practice — prime-order subgroups of $\mathbb{Z}_p^\ast$ or of an elliptic curve, whose order is a published parameter — you simply read $r$ off and go straight to the discrete-log Fourier sampling, skipping order finding entirely.

Why is ECC considered more vulnerable than RSA if both are "broken"?

Both fall to Shor, but the cost scales with the bit-length $n$ of the group order, and ECC deliberately uses a much smaller $n$ for the same classical security. A 256-bit curve matches the classical strength of RSA-2048, yet its quantum break needs roughly $6n\approx1500$ – $2300$ logical qubits against RSA-2048's $\approx4100$ , and correspondingly fewer reversible operations. What makes elliptic curves attractive classically — compact keys from a small, hard group — is exactly what makes them the cheapest quantum target, so ECDLP is likely the first public-key primitive to break, not the last.

Could Grover's search give the same exponential break of discrete log?

No. Grover's algorithm speeds up unstructured search only quadratically, turning a $\Theta(r)$ brute-force scan of exponents into $\Theta(\sqrt r)=\Theta(2^{n/2})$ — still exponential in the bit-length, and no better asymptotically than classical Pollard rho. The exponential break comes specifically from Fourier sampling exploiting the algebraic coset structure of the group, which Grover's oracle does not use. This is also why symmetric ciphers survive: with no algebraic structure to exploit, a $k$ -bit key loses only half its bits to Grover, so AES-256 retains $2^{128}$ security while DLP-based public-key crypto collapses to polynomial time.

If this breaks discrete log, why does lattice-based post-quantum cryptography survive it?

Because the exponential speedup is not generic — it is bought entirely by the abelian group structure that lets the quantum Fourier transform diagonalise the coset relation into a clean linear congruence. Lattice problems such as Learning With Errors and the shortest-vector problem do not present that structure; the relevant hidden-subgroup instances are non-abelian (for example the dihedral group behind certain lattice reductions), and no efficient quantum Fourier attack is known for them. That is the whole design principle of post-quantum cryptography: migrate to hardness assumptions that lack the algebraic symmetry Shor exploits. The new NIST standards (ML-KEM, ML-DSA) rest on lattices for exactly this reason, though their quantum hardness is a conjecture, not a theorem.