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 nontrivial) 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 1000digit
number, that would take the fastest existing supercomputer about 10 billion
times the age of the universe. But hope for the codebreakers 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 1000digit 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
