Why do we care about it?

Many encryption methods rely on how difficult it is to factor integers in very large numbers. Even with today’s super computers and cloud compute platforms, finding the factors of very large numbers can take decades or even centuries. The effort required protects the encryption. Shor’s algorithm promises to reduce that time significantly and threaten these types of encryption, given a large enough quantum computer.

How does it work?

Shor’s algorithm has two parts, a classical part and a quantum part. The classical part still loops through candidate possible factors as other algorithms do; however, the quantum part allows for more efficient parallel search for the answer based on the candidates, assuming that you have many qubits available. A qubit is a measure of the size of a quantum computer.

How close are we to being able to use it?

Shor’s algorithm has been tested with various types of today’s quantum computers and has successfully factored the numbers 15 and 21. Today’s quantum computers are small, numbering 10s of qubits. Since encryption algorithms like RSA240 use numbers 240 digits long (and others use larger), current quantum computers are not yet a threat to these encryption algorithms.

Is it really the end of encryption?

To crack encryption that uses integer factorization with very large numbers, we would need quantum computers 100s of times larger than today’s biggest quantum computers. Stable qubits are still difficult to build and simply aren’t available in large numbers. One can assume that this will change, but we are still decades away from the large stable quantum computers required for this task. In 2019, IBM built a 53-qubit machine. It is estimated that 4,000 qubits would be needed to efficiently crack RSA encryption using a 2,048 bit key.

Further, Shor’s algorithm was created in 1994 and there are encryption methods now in use that cannot be broken by Shor’s algorithm. That isn’t to say that other algorithms couldn’t break them, but by the time we have very large quantum computers, Shor’s algorithm will not be useful in breaking the encryption in use at that time. (See, for example, “Race is on to build quantum-proof encryption” by Adam Green, Financial Times, Nov. 19, 2019)