New generation of computers can break secret codes

Nevanlinna Prize winner Peter Shor has proved that factorising large numbers is possible at ultrafast speeds using quantum computers

At the opening ceremony of the International Congress of Mathematicians in Berlin on Tuesday, Peter Shor was awarded the Nevanlinna Prize for his pioneering work. This is the highest award available in mathematics for theoretical computer science. Today, Wednesday, he will be giving a plenary lecture to the international congress on quantum computing.

So far there have only been prototype quantum computers. They use the quantum states of individual atoms in their operations, which means that they can process many times more information than a traditional computer would be able to. In April 1998, researchers from IBM, MIT, the University of California in Berkeley and Oxford University reported that they had built a small quantum computer, using chloroform. A research group in Innsbruck, Austria is experimenting with ion traps. Experts estimate, however, that it will take at least a further two decades before there are functional quantum computers. There is therefore no danger yet for banks and internet users. "Scientists will have to solve a number of acute problems first, such as error stabilisation and control of the quantum states of this new computer. Peter Shor has also made fundamental suggestions here too," says Prof. Thomas Beth from the University of Karlsruhe. Together with physicists from Erlangen, Ulm and Magdeburg, Beth is one of the initiators of the Collaborative Research Programme: "Quantum information processing". set up by the Deutsche Forschungsgemeinschaft in May of this year.

By combining mathematical methods and the laws of quantum physics, quantum informatics promises to offer rapid solutions for classes of problem for which there have not previously been efficient methods for classical computers. It is precisely this sort of problem which encryption systems make use of. For example, the secret coding system developed in 1977 known as RSA (after its developers Ronald Rivest, Adi Shamir and Leonhard Adleman) makes use of the fact that it is relatively difficult for a conventional computer to divide a large number up into its factors. Shor has demonstrated that a quantum computer could be cleverly programmed to allow it to tackle this problem efficiently. He developed a new algorithmic principle for this, the so-called quantum parallelism. When factorising large numbers he uses the quantum-Fourier transformation and divides the calculation steps up into convenient partial transformations. A central element of the method is the tensor-parallelisation principle which was already used in the '80s for classical parallel computers.

Even though quantum computers do not pose a direct threat in the near future for encryption, e.g. for electronic cash or digital signatures, cryptographers are nevertheless already looking for new systems to use. The reason is that the secret codes which are used most frequently at the moment have a flaw - it is not possible to show mathematically how safe they are. It is only by increasing the length of public-keys step by step that it is possible to make it more complicated for code-breakers. With increasing computer speeds it is not a problem to lengthen the codes, but this does not alter their basic weakness. Quantum cryptography, on the other hand, promises absolute security. It also uses the principles of quantum physics. Light pulses are passed along an optical fibre; but anybody trying to intercept a quantum of light would immediately be detected. According to Heisenberg's uncertainty principle, one of the central principles in physics, it is not possible to observe a particle of this magnitude without altering the information that it carries.

Lecture by Dr. Peter Shor: "Quantum computing" - Wednesday, 19 August, 9.30 a.m., Venue: TU Main Building, Strasse des 17. Juni 135, 10623 Berlin, Auditorium Maximum