The basis for most of modern computer encryption—from government networks to the way you do online banking—is prime factoring, or reducing numbers to their lowest prime multipliers.
This can be done easily for smaller numbers—the factors of 14 are two and seven, for example, one can quickly deduce—but for larger numbers it gets increasingly hard. So hard that many of the world’s encryption systems have been built around it.
But what if you could build a computer that could quickly find the prime factors to large numbers? Even today’s supercomputers are far too inefficient for such a task, and scientists have long said that they would have to, in so many words, build a bigger, completely different kind of boat: a quantum computer, a machine based not on transistors but on atoms.
Such computers have been in development for decades, but, last week, scientists said they had made the most advanced quantum computer yet, using five atoms to successfully compute the prime factors of 15. They report that the bigger breakthrough, however, was that the computer was scalable, meaning that the problem was no longer physics, but technology and money. The implications, they said, could be huge, and put vast amounts of personal data, state secrets, and financial data at risk, in what would amount to quantum hacking.
“Well, one thing is that if you are a nation state, you probably don’t want to publicly store your secrets using encryption that relies on factoring as a hard-to-invert problem,” one of the scientists, Issac Chuang, says in a news release. “Because when these quantum computers start coming out, you’ll be able to go back and unencrypt all those old secrets.”
The computer was built by a team of scientists from the Massachusetts Institute of Technology and the University of Innsbruck in Austria. Underpinning the scientists’ work is Shor’s algorithm, formulated in 1994, which can be used to factor very large numbers given the proper quantum computer.
“We show that Shor’s algorithm, the most complex quantum algorithm known to date, is realizable in a way where, yes, all you have to do is go in the lab, apply more technology, and you should be able to make a bigger quantum computer,” Chuang says. “It might still cost an enormous amount of money to build — you won’t be building a quantum computer and putting it on your desktop anytime soon — but now it’s much more an engineering effort, and not a basic physics question.”