(InterestingEngineering) Peter Shor was a mathematician working for AT&T’s Bell Labs in 1994 when he first described his algorithm, known as Shor’s Algorithm–that required a technology that barely existed in theory, much less reality. The improbable technology Shor used, quantum computing, is not only advancing at a rate similar to Moore’s Law—-meaning that within a decade or two, quantum computers will be powerful enough to run Shor’s Algorithm and bust open RSA encryption. Shor’s algorithm itself helped inspire the development of quantum computing in the first place.
Peter Shor showed that a theoretical quantum computer could solve an intractable mathematical problem in ways that a classical computer never could by side-stepping the need to calculate single values at a time. Quantum computers can perform operations on qubits in superposition and literally reduce the time complexity of a problem exponentially.
By showing how a quantum computer could actually be useful in a way that classical computers couldn’t by solving a classically intractable problem in polynomial time, Peter Shor sparked the interests of researchers around the world who began their own research into quantum computing and now actual, working quantum computers are being built.