Shor's Algorithm - A breakthrough too good for its time.
What is Shor's algorithm and what applications does it have? Can Shor's algorithm really crack encryption efficiently? Are there any drawbacks and does it currently work on quantum hardware?
Short Summary?
Peter Shor is an American theoretical computer scientist who developed Shor’s Algorithm in 1994.
Shor’s algorithm rose to fame mainly due to its ability to quickly factorise huge numbers, making it a candidate for breaking worldwide digital encryption schemes (RSA).
In the face of this, numerous companies have started becoming ‘quantum-ready’ by preparing sophisticated quantum-resistant cryptography methods.
Shor’s algorithm uses a ‘hybrid’ approach, utilising both a quantum framework alongside a classical framework.
However, quantum computers do not have the current ability to run Shor’s algorithm, mainly due to the large number of error-corrected qubits required for successful implementation.
Introducing Peter Shor
As an American theoretical computer scientist born in 1959, it is perhaps not that surprising at all that Peter would come up with a revolutionary quantum computing algorithm. In 1977, whilst still at High School, he would place third in the USA Mathematical Olympiad and after graduation he would come second in an International Maths Olympiad. Peter graduated from Caltech in 1981 with a BSc and went straight to a PhD in mathematics at MIT - skipping a Master’s Degree. At Bell Labs in New Jersey, Shor would go on to develop Shor’s algorithm. This was around 1994. Shor also went on to propose multiple similar algorithms to target three problems in mathematics: the discrete log problem, the period-finding problem and the factoring problem.¹ These are all part of a larger mathematical group of problems known commonly as the hidden subgroup problem.² They are very prominent in quantum computing because in finding more solutions to this set of problems, new efficient quantum algorithms reveal themselves.
The buzz that Shor’s breakthrough caused would continue to spiral as he would receive award after award and fellowship after fellowship. However what might shock you is that Shor’s algorithm, even though it was developed over 30 years ago, is much more prevalent today then during its genesis. Quantum computation, in 1994 at least, was very much a theoretical prospect with next to no real quantum hardware. Now we live in a different age, where Quantum computers are currently growing large in number. Peter Shor theorised that if a large and powerful enough quantum computer existed, his algorithm would break the current standard of world-wide digital encryption. We are on the brink of bringing such a machine into existence.
Shor’s Algorithm without rigorous maths
We want an algorithm that can, given a large, odd number N that is not a prime power⁴, find N’s integer factors. In other words, we want to find what numbers make up our larger number. We must assume that N is odd, as if it is even, we instantly know that 2 is trivially a factor of N. In order to achieve this, Shor’s algorithm consists of two parts:
A classical step-by-step method.
A quantum operation to find the order⁵ of a sequence.
To start off with, make a random guess for a factor of our large composite number N. Make it larger than 2 but less than N itself. If you guess correctly then you may consider yourself incredibly lucky indeed, however most likely you will be wrong. Using Greek mathematician Euclid’s reasoning and logic, we know that if we compute the greatest common divisor (GCD) of any two numbers this will inform us of all their factors. If the greatest common divisor between the N and the number you pick is 1, this unfortunately means that we can consider these two numbers coprime as they share no non-trivial common divisors (as of course everything is divisible by 1). It also means that we are not informed of their factors either. And this is precisely the tricky case, where two numbers are coprime, since you can no longer use any classical methods other than pure guesswork. Pure guesswork is computationally costly.
By mathematical definition, the number that you guessed raised to some unknown power (call it x) will equal 1 modulus N.
For those unfamiliar, modulus refers to a sort of way of ‘bounding’ a number. For example, if we have a number y modulus 10, this means y can only ever be between 0 and 10. If it exceeds 10 or goes below 0 in any way, it will ‘wrap’ around back to the start - stuck forever in those bounds.
This is when the quantum part of our algorithm takes over, the part where we can efficiently find x. This part is incredibly complex and requires a strong knowledge of quantum circuits, so it is omitted here. After our quantum circuit outputs x, this allows us to recover a non-trivial factor of N. We must also state that our power x must be even, if it turns out to be odd, one must re-run the entire algorithm with a new guess. If indeed x is even, we may finally compute one more calculation classically and obtain two non-trivial factors of N. Complicated right? Below I’ll show what the quantum circuit looks like just for reference.
What you should take away from this is that, whilst this process seems lengthy and complex, it is in fact a lot easier than going through every single number classically in order to find factors of N.¹² What’s more, it has been shown that this algorithm will yield success after a few runs to a very high probability.¹⁴
RSA Encryption
The Rivest-Sharmir-Adleman (RSA) cryptosystem functions as one of the oldest but also most commonly used methods of digitally securing data. Back in 1977, these three cryptographers invented a ‘lock and key’ system allowing a user to safely keep their data private.
It works like this: a large public encryption key is published and acts as a sort of doorman for a database. The private decryption key is the password one must give to the doorman, without it there is no entry. The public key is a huge composite number, made from the multiplication of two rather large prime numbers. What this means is that only a user who knows what these two prime numbers are can break the lock and enter in. This continues to be quite a secure system as factorising the product of two large prime numbers requires that you know exactly what these numbers are - any other number will not be a factor of the public key.
However, this is precisely why Shor’s Algorithm has generated so much buzz - it details a much quicker and easier method of finding the factors of a large composite number N. According to some sources, a classical computer that would take 300 trillion years to decode an RSA key would theoretically take only about 10 seconds on a quantum computer.⁷ This is quite a scary prospect, and whilst it remains only in theory today, most large companies are already changing their encryption methods in order to make them ‘quantum-safe’.¹³ As such, research on a new field known as post-quantum cryptography has started to bloom. In my opinion this might be one of the most compelling reasons as to why quantum funding initiatives have spiked to enormous magnitudes.
Business leaders must be bold and innovative—two of the Art of Smart’s pillars of success—and proactive to address the security concerns presented by quantum computing, ensuring that they are well-equipped to mitigate risks and protect their organizations.⁷
The up and coming ‘quantum apocalypse’ is further dramatized by the fact that there will indeed be people out there already collecting RSA encrypted data and storing it on large computers. This is known as a ‘Harvest now, decrypt later’ threat, where the attacker collects sensitive locked data and holds it. Even though the ability to quickly decrypt RSA data doesn’t exist yet, one can simply wait until it does exist and then apply it to the data they already have stored on their machines. We shouldn’t be scared of such a prospect, just prepared.
So why doesn’t Shor’s Algorithm work just yet?
Unfortunately, quantum computers aren’t quite up to the task just yet. In 2001, IBM factored the number 15 successfully.⁸ In 2012, the Center for Quantum Photonics implemented a photonic-qubit algorithm to factor the number 21.⁹ In 2019, however, the attempt to factorise 35 failed precisely because of a large number of accumulating qubit errors. As of current, there have been no successful attempts at factorising a truly large number - which is the crucial boundary between breaking and not breaking RSA encryption.
The theory that I have just outlined above assumes a noiseless and error free quantum computer, something which quantum error correction cannot fully provide. In order to perfectly run Shor’s algorithm, one would need a completely robust error correction scheme. There are many estimates about the resources required to pull off this feat - this is again quite a tough thing to estimate. Depending on the type of quantum computer, the type of quantum circuit being used and the (rather ingenious) shortcuts that can be made, the actual resources required to run Shor’s algorithm vary massively. Certain academic papers state that it could take 2n+2 logical qubits, where n is the desired password bitstring size,¹⁵ meaning this would require 448n^3log₂(n) number quantum ‘gate’ operations and this would also assume that the qubits are being constantly error corrected, ergo: logical qubit. This roughly translates to 2050 logical qubits, a huge milestone to reach, assuming n is a normal RSA bitstring size of 1024.¹⁰ Furthermore, this would theoretically demand over 4 trillion gate operations… circuits of this sort of depth will be incredibly challenging to run.
To conclude
It is not an exaggeration to say that Peter Shor’s algorithm is a bit too good for its time. This algorithm is one of the few quantum algorithms with compelling evidence that it can demonstrate quantum advantage over classical methods. In theory, the algorithm has the potential to factorise large numbers and indeed would allow for a dramatic decrease in the amount of time required to break RSA encryption. This is countered by the practical world, in which the limitations outlined for successful quantum computation are numerous.¹¹ Quantum computing scientists must therefore battle against decoherence due to noise, against error correction, against qubit counts and finally against the many other technical impracticalities associated with Shor’s algorithm. For now, Shor’s algorithm remains theoretically ‘golden’ rather than an actual threat to modern-day encryption.
Footnotes:
The Discrete Logarithm Problem outlines how it is generally hard in large groups to find an integer x: given α, β ∈ G, compute log(α) β if β ∈ <α> and otherwise report that β is not ∈ <α>. The Factoring Problem outlines, and for some numbers especially, the difficulty of expressing a large number as a multiplicative expression of all its prime factors. The Period-Finding problem outlines the general difficulty of finding the period of any repeating arbitrary function, especially when the ‘period’ (how long until it repeats) is incredibly large.
Accessed from here. (note: Peter likes a lot of poetry)
A prime power is a prime number that is raised to an integer power. The reason why we should not consider N to be this is because there is a purely classical method to efficiently solve for this.
The order of a sequence is the number of entries in a sequence until it repeats.
Accessed from here.
Accessed from here. It should be noted, however, that quantum computers currently have neither the necessary number of qubits nor a good enough error correction system.
See arXiv.
See arXiv once more.
See this paper.
A paper showing that current factorising on quantum computers remains hard to implement.
Do note, budding scientists, that there are more efficient classical methods than going through every single number… but the scaling of Shor’s algorithm is polynomial, whereas the most efficient classical factoring algorithm is sub-exponential (worse).
IBM, Microsoft, Google, Cloudflare etc.
Do read this if you are interested!
A bitstring is basically, as it sounds, a string of bits. This is a new type of language for those unfamiliar, originating from binary code. Binary code has two types of symbols, the 0 and the 1. And each unique combination of ‘0100’ or ‘1110’ or whatever, represents an actual number. For eg. ‘111’ = 7.
Photo accessed from here.
“In 2012, the Center for Quantum Photonics implemented a photonic-qubit algorithm to factor the number 21”
You realize 21 = 42/2?
This result may be more amazing then you imagined!
More food for thought as your paper highlights that we sometimes half to wait for technology/hardware to catch up surrounding the theories.