3 Why Quantum Computers Break Some, But Not All, Cryptography (2026-08-14)

This post’s ID is 3555430289526188340.

There is a remarkably common misconception (one I’ve personally run into a few times) that quantum computers break cryptography by, essentially, making brute-force search work in polynomial time. I cannot be clear enough when I say this is not true, and this is not how quantum computers work. If it was true, there would no longer be a cryptography. It would also, amusingly, imply that P is NP for quantum computers.

Quantum computers are fundamentally not that different at a mathematical level than classical computers. However, explaining the difference is going to require a bit of mathematical background. I will assume basic familiarity with linear algebra (but not modern algebra, for which I’ll explain concepts).

3.1 What is a field?

A field is a mathematical object consisting of a set associated with two operations, conveniently (but not always) referred to as multiplication and addition. These operations must satisfy certain properties:

• Both multiplication and addition must be closed over the field, which is to say $ab$ is in the field if $a$ and $b$ are (and likewise with $a + b$).
• Both multiplication and addition must be commutative: $a + b = b + a$ and $ab=ba$.
• Both multiplication and addition must be associative: $a(bc)=(ab)c$ and $a + (b + c) = (a + b) + c$.
• There must exist two distinct and unique identity elements $0$ and $1$ such that $a + 0 = a$ and $1(a) = a$ for all $a$ in the field.
• For multiplication, there must be for each nonzero element $a$ an element $a^{-1}$ such that $aa^{-1}=1$.
• For addition, there must be for each element $a$ an element $-a$ such that $-a + a = 0$.
• Multiplication must distribute over addition: $a(b + c) = ab + ac$.

You might think this is just, like, all numbers, and that I’m pulling your leg, but enterprising young mathematicians should note that these properties do not hold for all subsets of the complex numbers (like, say, the integers $\mathbb{Z}$!).

3.2 What is a Galois field?

This is where things get slightly more fun. See, there are infinite possible fields with infinite members (like the rational numbers $\mathbb{Q}$), but there are also infinite possible fields with finite members! These are termed Galois or finite fields, after the 19th-century French mathematician Évariste Galois. We can think of a trivial Galois field right off the bat: $\mathbb{F}_2$, the Galois field with two elements, zero and one (if we assume here that $1 + 1 = 0$). You can confirm for yourself that the above properties hold. The number of elements in a Galois field is termed its order, and must be a nonzero power of a prime number.

Why?

Assume that we have a field $\mathbb{F}_q$ with order $q$.

Let $f(s) : \mathbb{Z} \to \mathbb{F}_q$ be equal to adding the $1$ element to itself $s$ times. Then there exists $1 \leq k \leq q$ such that $f(k) = 0$ (we call this the characteristic of $\mathbb{F}_q$). If there are multiple such $k$, then we take the smallest one. At least one such $k$ must exist by the pigeonhole principle and the fact that the $0$ and $1$ elements must be distinct.

If $k$ was composite, then we could take any prime factor $k_1$, and adding $f(k_1)$ to itself $k/k_1$ times would equal zero: by distributivity, we can equate this to $f(k/k_1)f(k_1) = f(k) = 0$. Doing this for every prime factor (with repetitions), we obtain $f(k_1)f(k_2)\cdots f(k_n) = 0$, of which no $f(k_i) = 0$ (since $k$ is specifically the smallest integer with that property). Each of these $f(k_i)$, being nonzero, has an inverse $f(k_i)^{-1}$, and if we multiply $[f(k_1)f(k_2)\cdots f(k_n)][f(k_1)^{-1}f(k_2)^{-1}\cdots f(k_n)^{-1}]$, we could arrive at $0$ or at $1$ by following either the distributivity or identity properties. Both cannot be true, so we have derived a contradiction, so $k$ must be prime.

Now we must show that $q$ is a power of $k$.

If $k$ does not divide $q$, then we would see that $f(q) \neq 0$, $f(2q) \neq f(q) \neq 0$, and indeed $f(aq), 1 < a \leq k$ covers every element of $f(a), 1 < a \leq k$. Therefore, assuming without loss of generality that $q - k < k$, $f(a) + f(q - k) = f(aq), 1 < a \leq k$. Setting $a = k$, we obtain $f(k) + f(q - k) = f(kq) = f(k)f(q)$, so $f(q - k) = 0$, which cannot be true. Thus $k$ divides $q$.

Now assume that $q$ has some prime factor $q_1 \neq k$. We see easily that $f(aq_1) \neq 0, 1 < a < k$, and also that $f(aq_1) \neq f(bq_1), 1 < a < k, 1 < b < k, a \neq b$. Take $d$ to be the absolute value of the difference between $q_1$ and the nearest nonzero multiple of $k$. $d < k$, so $f(d) \neq 0$, and $f(aq_1) = f(a) + f(d), 1 < a \leq k$. As before, set $a = k$ and observe therefore that $f(d) = 0$, which is a contradiction, so $q$ must be a power of $k$.

3.3 How do classical computers work?

There are several equivalent models of classical computing, as presented by Alan Turing, Haskell Curry, and others. However, we will presently restrict ourselves to a model that is actually not equivalent to any of these, as it doesn’t allow for unbounded computation (in addition to other things). We can, though, take this model and extend it to a full Turing-complete model of computing.

Brief terminology note

A linear operator is a generalization of a matrix that takes into account only what it “does” to a vector.

Let’s say that a classical computer is a linear operator $A$ over a vector space $V$ associated with scalar field $\mathbb{F}_2$. The members of this vector space are each of the form $[a_i e_1 + b_i e_0]^{\otimes n}, (a_i, b_i) \in\mathbb{F}^2_2$, where $e_1$ is a basis vector representing a $1$ and $e_0$ is a basis vector representing a $0$. We can then add vectors by adding up their “subvectors” in an elementwise fashion using this handy-dandy table:

So every element is its own inverse. We will see that it does not matter that $e_1 + e_0$ does not have any physical interpretation for a classical computer. We then define a linear operator $Gx: V \to \mathbb{F}_{2^n}$ such that $(Gx)_i = 1$ if and only if the subvector $x_i$ is either $e_1$ or $e_0$, with $(Gx)_i = 0$ otherwise. Essentially, $(Gx)_i$ indicates if a subvector corresponds to a physically achievable state. $G$ is a linear operator, because $Gx + Gy = G(x + y)$ for all $(x, y)\in V^2$, but it is not invertible.

We can then clarify that $A$ has the restriction that $GAx = Gx$. If we only feed in $x$ such that $Gx = \vec{1}$, i.e. all of our input vectors correspond to physically achievable states, then $Ax$ will always give out corresponding physically achievable states. We can thereby represent any bounded classical computation as a linear operator with this property.

Why not just use $0$ to represent $0$ and $1$ to represent $1$?

Representing $0$ and $1$ as basis vectors makes it so that all the basic logic gates can be represented using a modification of the Toffoli gate, thus being linear operators with $GAx = Gx$, which means their composition is also a linear operator with this property. This requires some extra machinery when extended to a Turing machine, but it is entirely possible.

We can extend this to be directly equivalent to a Turing machine by assuming that the internal state register of the machine corresponds to a vector $s$ such that $Gs = \vec{1}$, the symbols on the tape are (perhaps differently-dimensioned) vectors with the same property, and the output action of the machine is a vector with that property. Then we can describe the state machine as a bounded classical computation, which we represent as a linear operator $A$ with $GAx = Gx$, and this gives us a Turing complete model.

Why did I make this so complicated? So as to make quantum computers seem vanishingly simple by comparison.

3.4 How do quantum computers work?

By taking the previous description and replacing the scalar field $\mathbb{F}_2$ with the complex numbers. Now, the vector space is given by $[a_i e_1 + b_i e_0]^{\otimes n}, (a_i, b_i) \in \mathbb{C}^2$. Instead of using $GAx = Gx$, to indicate that a vector corresponds to a physically achievable state, we check that $||x|| = 1$, and we assume that $A$ is unitary (i.e., its Hermitian transpose is its inverse and thus the magnitude of its determinant is 1) and thus preserves this property. You can verify that this can compute anything the classical model can on your own time.

Wasn’t that easy?

It turns out to have massive implications, including making possible a couple algorithms that do certain problems that are hard for classical computers very quickly.

But first, a brief diversion.

3.5 When are logarithms hard?

Finding the logarithm base $a$ ($a \in \mathbb{N}$) of a positive integer $a^b$ is simple and can be done quickly enough using simple bisection:

1. Start with the numbers $l := 0$ and $h := a^b$.
2. Compute $m := a^{(l + h)/2}$. If $m$ is lower than $a^b$, set $l := \lfloor (l + h)/2 \rfloor$; if it’s higher, set $h := \lfloor (l + h) / 2 \rfloor$; otherwise, return $\lfloor (l + h)/2 \rfloor$.
3. Repeat step 2 until you return.

This algorithm works because $a^x, a > 1$ increases monotonically as $x$ does. Can we generalize logarithms to cases where this isn’t true?

We can. The discrete logarithm assumes $b$ is a nonnegative integer and lets us generalize logarithms to groups generally.

What is a group?

A group is like a field as defined above but doesn’t have an addition operation (and thus a zero element) and multiplication doesn’t need to be commutative (though you could equivalently say it doesn’t have multiplication or a one element and addition doesn’t need to be commutative).

To explain briefly why discrete logarithms often aren’t as easy to find as regular logarithms, note that the above algorithm relies on an unstated property of $a^x$ over the reals: it’s continuous in addition to being monotonically increasing for $a > 1$. This means we can apply one of my favorite theorems from my scientific programming class in college, the intermediate value theorem.

Unfortunately, we can’t generally assume that a group even has a concept of continuity to apply. To make things worse (it can always get worse), we cannot assume that exponentials are monotonically increasing or decreasing. Why?

Consider the Galois field $\mathbb{F}_{127}$. We can represent this really easily as the integers modulo 127: that is, we take the integers and consider any two $a$ and $b$ to be congruent if and only if there exists an integer $c$ such that $a = b + 127c$. If we then consider all congruent integers to be the “same” as each other, we can see that this forms a field.

Now let’s plot out $3^x \pmod{127}$ for $x$ from 0 to 126 inclusive. You might see where this is going.

Definitely not monotonic. You can check, though, and see that every member of $\mathbb{F}_{127}\setminus\{0\}$ is represented; in fact, since 127 is prime, there is no base whose powers will ever include zero. That all the members are represented is not going to be true of every element of $\mathbb{F}_{127}$. It isn’t true of 2, for example. The number of unique elements of a group that can be generated by multiplying/adding an element $x$ by itself is, confusingly, termed the order of $x$ (it helps that this is because those unique elements themselves form a group, and that’s what the order is referring to here).

When are discrete logarithms easy to find?

There are a few notable cases, but in short: division over a Galois field of prime order is a special form of the discrete logarithm, and it’s easy in large part because of Euler’s theorem allowing us to compute $a^{-1}$ for $a \in \mathbb{F}_q$ as $a^{q-2}$, which can be done as a series of multiplications.

You will note that I am not giving any rigorous proof that this problem is hard, only that it’s not solvable by the simplest algorithm for solving non-discrete logarithms. This is because we actually don’t really know if this problem is truly hard for classical computers, but we think it is. We do know, however, that it is easy for quantum computers using Shor’s algorithm.

3.6 Shor’s and Grover’s algorithms

There are two quantum algorithms that cryptographers (generally) care about. One is called Shor’s algorithm (due to mathematician Peter Shor), and the other is Grover’s algorithm (due to mathematician Lov Grover). Note that if you understand how quantum computers work, Wikipedia generally explains these more succinctly and clearly than I could here, so go read that.

The exact details don’t super matter here: just know that Shor’s lets us factor large numbers and compute discrete logarithms quickly on a quantum computer, and that Grover’s lets us reverse an arbitrary function a little less slowly (if there are $N$ possibilities, Grover’s needs on the order of $N^{1/2}$ steps where classical brute-force search needs $N$ steps). They both do this by taking advantage of the expanded number of states a quantum computer allows.

How are factoring and discrete logarithms related?

Shor’s algorithm actually technically solves the hidden subgroup problem, of which factoring integers and computing discrete logarithms are special cases.

3.7 Who cares about discrete logarithms?

You should. The problems solved by Shor’s are the hard problems underlying RSA, Diffie-Hellman key exchange, and (most) elliptic curve cryptography. When cryptographically-relevant quantum computers come around, they will be used to break these primitives and we need to have moved to primitives that aren’t as easily broken by them.

Wait, you mentioned Grover’s algorithm. Is that relevant here?

It’s a long story, but essentially Grover’s is faster than brute-force search, but not enough to actually break any real cryptography (that I know of). The reason we want something in classical cryptography to take around $2^{128}$ steps or more to break is because usually, those steps can be parallelized, so if it took $2^{64}$ steps we could throw a supercomputer with $2^{16}$ CPUs at the problem and crack it in a few years. The way Grover’s works, however, means that if you parallelize it it actually takes more steps overall, to the point where a quantum computer or group of quantum computers will likely never be able to break 128-bit symmetric primitives unless they are also broken classically! There is an excellent blog post by Filippo Valsorda that covers this if you want a more in-depth explanation.

3.8 Wait, why are elliptic curves broken?

Most (but not all!) elliptic-curve cryptography essentially relies on the discrete log problem over elliptic curves.

What’s an elliptic curve?

For some field $K$, we take an elliptic curve in homogeneous coordinates to be the set of points $(X, Y, Z) \in K^2 \times \{0, 1\}$ of the equation $ZY^2 = X^3 + aZ^2X + bZ^3$ for some coefficients $(a, b) \in K^2$. Note that we omit the solution $(X, Y, Z) = (0, 0, 0)$ because, in projective geometry, $Z = 0$ denotes the “point/line at infinity”, which doesn’t have a super intuitive physical meaning but makes the math much nicer and makes each elliptic curve form an abelian group (which is a group where we can assume the group operation is commutative).

An elliptic curve over a Galois field forms an abelian group with a finite order. To add two points $P$ and $Q$ on the curve, we draw a line through them, find the third intersection with the rest of the curve (which may be on the aforementioned line at infinity), and flip that point across the $X$-axis, giving us $P + Q = R$. By repeatedly adding a point to itself or negating it, we can “multiply” the point by an integer; this is termed scalar multiplication. We can therefore formulate the discrete logarithm problem for elliptic curves: take $1 \leq a \leq L$, $L$ being the order of the “base point” $B$, and given $aB$, compute $a$. In fact, if $L$ is prime, then the group generated by scalar multiplication of $B$ is isomorphic to the integers modulo $L$.

3.9 Conclusion

Quantum computers are complicated but not that different fundamentally from classical computers. Nevertheless, certain problems that are hard on classical computers and on which we placed several decades of cryptography are easily broken by quantum computers. This includes RSA, Diffie-Hellman key exchange, and scalar multiplication on elliptic curves. I hope this primer was enough to at least generally explain why all this is true.

Comments