Summary

Shor’s algorithm is the crowning glory in the theory of gate-based quantum computing. Using Shor’s algorithm, a quantum computer can do what no classical computer could ever have time to do. The algorithm quickly finds the period of a coprime powers sequence and uses information about that period to factor unimaginably large numbers. That’s the good news.

The bad news is that the most obvious use of Shor’s algorithm is for unsavory purposes. Many applications in use today include some form of RSA encryption. And with Shor’s algorithm, a hacker can easily break the RSA encryption scheme. For this reason, the National Institute of Standards and Technology (NIST) in the United States has been running an initiative to develop quantum-proof post-quantum cryptography schemes [4]. Someday, in the not-too-distant future, the battle over your security and privacy will be fought with quantum computers and even more robust cryptographic algorithms...