Get the latest tech news

A Quantum Leap in Factoring

In the mid-1990s, Peter Shor, at AT&T Bell Labs and then one of its heirs, AT&T Labs, devised the first algorithms that one day could exploit the intrinsic parallelism of quantum computing. In particular, Shor, now at the Massachusetts Institute of Technology (MIT), showed that quantum techniques could be exponentially faster than any classical computer at finding the factors of a very large number, a task whose difficulty is key to the security of widely used public-key cryptography techniques.

“There are a few other algorithmic ideas out there,” said Oded Regev of New York University, but “nothing is as exciting as Shor.” Over the decades, researchers have found ways to significantly reduce the resources required for factoring, but the size needed to crack secure cryptography is still far beyond current quantum hardware’s capability. This extension was “a pleasant surprise,” Regev said, and “a very clever trick.” By efficiently using reversible operations to re-use hardware, this multiplication scheme can reduce the required number of qubits to order n, the same asymptotic size-dependence as improved versions of Shor’s algorithm. “The constants matter,” emailed Martin Ekerå, a cryptographer for the Swedish government, whom Regev described as “the world expert in implementing Shor’s algorithm.” For example, huge 2,048-bit numbers often are used in the Rivest-Shamir-Adleman (RSA) public-key cryptography framework for current applications, but that is not necessarily big enough for the asymptotic advantage to become clear.

Get the Android app