Whether we realize it or not, cryptography is the fundamental building block on which our digital lives are based. Without sufficient cryptography and the inherent trust that it engenders, every aspect of the digital human condition we know and rely on today would never have come to fruition much less continue to evolve at its current staggering pace. The internet, digital signatures, critical infrastructure, financial systems and even the remote work that helped the world limp along during the recent global pandemic all rely on one critical assumption – that the current encryption employed today is unbreakable by even the most powerful computers in existence. But what if that assumption was not only challenged but realistically compromised?
This is exactly what happened when Peter Shor proposed his algorithm in 1995, dubbed Shor’s Algorithm. The key to unlocking the encryption on which today’s digital security relies is in finding the prime factors of large integers. While factoring is relatively simple with small integers that have only a few digits, factoring integers that have thousands of digits or more is another matter altogether. Shor proposed a polynomial-time quantum algorithm to solve this factoring problem. I’ll leave it to the more qualified mathematicians to explain the theory behind this algorithm but suffice it to say that when coupled with a quantum computer, Shor’s Algorithm drastically reduces the time it would take to factor these larger integers by multiple orders of magnitude.
Prior to Shor’s Algorithm, for example, the most powerful computer today would take millions of years to find the prime factors of a 2048-bit composite integer. Without Shor’s algorithm, even quantum computers would take such an inordinate amount of time to accomplish the task as to render it unusable by bad actors. With Shor’s Algorithm, this same factoring can potentially be accomplished in a matter of hours.
