Much of modern cryptography and the way we keep digital data, such as online banking transactions, secure from prying eyes, relies on what are called trapdoor one-way functions. Cryptography is the process of encrypting and decrypting data. We can think of encryption as a function and decryption as the inverse of that function.
A one-way function is a function that is quick to compute for any input, but which is computationally difficult to invert; that is to say given an output of the function, it is computationally difficult to find the input of the function that would result in that output. So, a one-way function is very useful in encrypting data. However, we need a way for some people—just the people we want—to be able to invert the function, that is, to decrypt the encrypted data.
A trapdoor one-way function is the key to such a cryptosystem. A trapdoor one-way function permits a hint as to how to invert it. With this hint, the one-way function is no longer one-way—it is in fact easy to invert. Otherwise, without the hint, the function is a one-way function that's easy to compute in one direction and hard to compute the inverse. This means to all but those who possess the hint data can be encrypted, and only those with the hint, known as a secret-key in a cryptosystem, can decrypt the data.
One particularly popular cryptography system, the RSA algorithm, relies on a trapdoor one-way function involving the product of two primes to create what is called a semiprime number. Semiprimes are a great candidate for a one-way function as they are the hardest factorization case.
It is easy to compute the product of two prime numbers. For example, the product of the prime numbers 533,000,401 and 86,028,157 can be quickly computed in Python to be 45,853,042,178,290,957, but figuring out which primes multiply together to yield 45,853,042,178,290,957 is computationally tricky; thus this is a one-way function. However, given a hint, for example, that one of the two prime factors is 533,000,401, it becomes quick to compute again. Simply divide 45,853,042,178,290,957 by 533,000,401 to get the other prime; thus, this is a trapdoor one-way function. RSA uses primes so large that to factor their product without a hint on a classical computer could take more than a quadrillion years, for example, much longer than the age of the universe. The best known classical algorithm for factoring a semiprime integer into the product of two primes runs in time O(exp(d1/3 )), where d is the number of decimal digits of the integer to factor, for example, for 45,853,042,178,290,957, d = 17. The record for d at the time of writing this book is around 200.
Any algorithm that has computed the prime factorization of a large integer efficiently, figuring out which two primes multiplied generated it, would ruin the one-way nature of the product of two primes. The RSA cryptosystem relies on this one-way nature, and so its cryptography would be broken in this scenario. This would have real-world consequences: since the RSA cryptosystem powers many secure financial transactions on the internet, these transactions would no longer be secure. Shor's algorithm can run on a quantum computer that runs in polynomial time instead of exponential time; specifically, it runs in O(d3)), unlike the best-known classical algorithm, which runs in O(exp(d1/3 )).
New cryptosystems cannot be designed and deployed that are not vulnerable to Shor's algorithm, but that has not stopped the flurry of research and hope on the part of nation states that a quantum algorithm could give them unique access to encrypted data for the purposes of national advantage for offensive or defensive cyber operations. Since Shor's algorithm's existence shows that quantum computing can have a disruptive impact on real-world classical technology, it has resulted in the hope that many more quantum computing algorithms can be designed to show such disruptive potential.