In 2001, a quantum computer was able to factor 15.
In 2012, a quantum computer was able to factor 21, sorta. They cheated by not implementing gates that they knew a priori would not be used. To this day, there still hasn’t been a quantum computer to factor 21 without taking some shortcuts. Some reasons why are given here.
Extrapolating from two data points is kinda ridiculous, but we only have two data points, and we’re going to do it anyway.
Some may object that extrapolating the size of the numbers that can be factored isn’t the right approach. Instead we should be extrapolating the number of qubits or something else. Fine, but that’s not what we’re doing in this post.
Linear interpolation
Using linear interpolation, a quantum computer wouldn’t be able to factor a cryptographically relevant prime number before the heat death of the universe.
Exponential interpolation
Let’s switch to exponential extrapolation. Instead of assuming the size of the numbers grows linearly, we’ll assume the number of bits in the numbers grows linearly, meaning the numbers grow exponentially.
In about 10 years, the size of number that could be factored increased by
21/15 = 1.4 ≈ √2.
This means the size of the numbers increased by about half a bit in a decade. By now we should be able to factor 35.
RSA keys have at least 1024 bits, so at half a bit per decade, quantum computers should be able to factor RSA keys 20,000 years from now.
Double exponential interpolation
Now let’s assume the number of bits in a number that a quantum computer can factor is itself growing exponentially, meaning that the numbers are growing doubly exponentially, doubling every decade. Then we should be able to factor 9-bit numbers by now, and in 100 years we will be able to factor RSA keys.
Breaking RSA in 10 years
The estimate above kinda arbitrary because a double exponential function has three degrees of freedom and so we’d need three data points, which we don’t have.
We can fit a double exponential by making up a third data point. Some researchers speculate that a quantum computer will be able to factor 1024-bit RSA keys 10 years from now. If so, that gives us a third data point.
To make things easier, let’s work in terms of bits and set x to be the number of years since 2000. Then we have
f(x) = a + b 2cx
with f(1) = 15, f(12) = 21, and f(35) = 1024. We can fit this function using Python.
from scipy.optimize import curve_fit
def f(x, a, b, c):
return a + b * 2**(c*x)
x_data = [1.0, 12.0, 35.0]
y_data = [15.0, 21.0, 1024]
initial_guess = [7, 8, 1.0/35]
popt, pcov = curve_fit(f, x_data, y_data, p0=initial_guess)
a, b, c = popt
print(f"Fitted parameters: {a=}, {b=}, {c=}")
# confirm fit
print([f(x, a, b, c) for x in x_data])
The parameter values are a = 14.405426257249923, b = 0.4777574337110432, and c =0.31557743199546157.
Here’s a plot of the fitted function f.
If we’re going to be able to factor 1024-bit integers by 2035, according to a double exponential model, we’re already behind schedule. We should be factoring 128-bit numbers by now, but so far we’ve only factored a 4-bit number.
Or to put it another way, those who believe we will be able to factor 1024-bit integers by 2035 are implicitly assuming a future rate of growth faster than double exponential. And maybe they’re right.
If we’re going to break 1024-bit RSA keys by 2035, at some point we’ll have to do better than the curve above, and so far we’re doing worse.
Bookmark this post and come back when a new quantum factoring record is set and rerun the code with new data.
Related posts
The post Extrapolating quantum factoring first appeared on John D. Cook.