Undoing the cryptographers' work
(March 1998)



Modern methods of encrypting computer data rely on the problems we encounter in trying to find all of the factors of a large number which is the product of two primes. To take a simple (but non-trivial) example, the number 1729 has three prime factors which are in arithmetic progression, making it one of an interesting subset of the Carmichael numbers, but even finding the small factors of such a simple number can take a human quite a while.

Computers can do it faster, but if you ask a computer to factorise a 1000-digit number, that would take the fastest existing supercomputer about 10 billion times the age of the universe. But hope for the code-breakers may be on the way, sooner or later.

The trick is to develop a quantum computer, which nobody has done yet. Rut when the first quantum computer is unveiled, the algorithms will be there to help program it, including an algorithm which would factorise the 1000-digit number in about half an hour!

Described in the 16 March issue of Physical Review Letters, this algorithm could dramatically speed up chores like searching through reams of data, especially in scheduling problems where teachers and students have to be fitted into a timetable with no clashes. The limitation in doing this on an ordinary computer is that each item must be in binary form, coded as a single bit which is either on or off, 1 or 0.

A ''bit'' in a quantum computer can have more than one state at a time, represented by the quantum characteristics of a particle like an electron or photon. This means that a string of quantum bits can hold all possible schedules at the same time. when the quantum states of the particles are measured, this forces the system to choose one of the possible configurations, one of the schedules. Each schedule has a probability of being chosen. and this can be set to depend on havina the smallest number of conflicts. The algorithm is the work of Tad Hogg of the Xerox Palo Alto Research Center in California. Even if quantum computers are years away from being built, studying quantum algorithms clarifies the nature of problems by probing their structures ever more deeply - and it may just turn out to be useful to those who design the new forms of computer, sometime in the 21st century.

©WebsterWorld Pty Ltd/contributors 2002


MAIN INDEX

REFERENCE GUIDE

TRANSCRIPTS

GLOSSARY

Maths Physics Biology Chemistry Computing Science Electronics Belief Art Philosophy

www.000webhost.com