Cryptography Reference
In-Depth Information
methods became insecure
. The computational speed versus algorithms currently
known would accelerate exponentially. It is currently possible that a 512-bit
RSA key could be broken on conventional computers, and 768 bits should be
possible with the Twinkle device introduced in Section 4.5.3. Cracking 1024-bit
keys is definitely utopian with such methods and current computing technol-
ogy. If we had quantum computers, for example, 1024 bits would take only
twice or four times as long as 512 bits. And that's thought to be fast, really
fast — perhaps in the range of seconds or minutes.
Quantum computers could be useful for other tasks, too. For example, searching
unordered data repositories is one of the most time-consuming tasks for current
computers. It generally takes
n
/2 steps to find a specific record from a list of
n
records. In his article included on our Web site (
txt/quant/qc-grover.txt
), Grover
explains an algorithm for quantum computers that needs only
√
n
steps. More
specifically, while a conventional computer requires 500 billion steps to find
a specific entry out of one trillion entries on average, a quantum computer
with Grover's algorithm can do this in about one million steps — 500 000 times
faster. Grover even shows that it cannot be faster than that in general on a
quantum computer.
Finding periods of functions is much faster on quantum computers compared
with using classic algorithms. This is the special feature that methods for fac-
toring and computing discrete logarithms are based on. Rather than working
sequentially, quantum computers truly work in parallel.
Back to Reality
Unfortunately, there is no single quantum computer yet, at least not one that
deserves this name. One of the large number of hurdles has been that quantum
computers don't work deterministically, which means that they are error-prone.
This problem was solved by Shor and Steane at the same time in 1995. They
designed methods for error correction in quantum computers which obviously
nobody had believed in.
In August 2000, Isaac Chuang of the IBM Almaden Research Center presented
the most promising approach to that date in a cumbersome manner to the
press: a glass tube with special molecules, in which atomic nuclei simulated a
5-qubit quantum computer, triggered and read by electromagnetic waves based
on nuclear magnetic resonance (NMR) imaging. In effect, this computer can
process a very short algorithm. Insiders will want to know that the qubits
correspond to the spins of single atoms in specially constructed molecules
coupled over electron sheaths (so the algorithm lies obviously in the molecular
