Information Technology Reference
In-Depth Information
Fig. 15.17. Factorizing RSA-129. This
graph shows the increase in comput-
ing power, measured in numbers of
computer instructions, required to
factorize larger and larger numbers,
measured in numbers of bits. For a
classical computer, the required power
grows exponentially with the number
of bits in the number to be factorized.
The importance of Peter Shor's quantum
algorithm was that it showed that with a
quantum computer, the required power
grows only as the cube of the number of
bits. Also shown is the 129-digit number
RSA-129 that was factorized in 1994 by
volunteers using about 1,600 computers
over several months. A quantum com-
puter operating at the same speed as just
one of these machines could factorize
the number in only a few seconds.
Classical
~ exp{A[L
1
/3
In
2/3
L]}
1�10
24
1�10
23
1�10
22
1�10
21
1�10
20
1�10
19
1�10
18
1�10
17
1�10
16
~10
17
instructions:
8 months
1�10
15
1�10
14
1�10
13
Quantum
~ L
3
1�10
12
1�10
11
1�10
10
1�10
9
1�10
8
1�10
7
~10
10
operations:
seconds
1�10
6
1�10
5
1�10
4
1000
100
10
1
0
200
400
600
800
1000
Number of bits, L,
factored
RSA-129
Conventional computers are very good at multiplying two numbers
together. For example, the time taken to multiply two N digit numbers grows
as the square of N. By contrast, the time needed to
factorize
an N-digit number -
that is, to resolve the number into two smaller numbers that when multiplied
together form the larger number - grows faster than any power of N. This is an
example of a
one-way function
, as explained in our discussion of public-key cryp-
tography in
Chapter 12
. A one-way function is a mathematical problem that is
easy to solve in one direction, but difficult or even impossible to solve in the
other. For example, it is easy to multiply together two large
prime numbers
(num-
bers divisible only by themselves and 1). However, if you give the huge number
resulting from that multiplication to someone else and ask him or her to tell
you what numbers you started with, this problem is very hard. Shor showed
that a quantum computer could, in principle, factorize numbers just as easily as
it multiplied them, without the computing time increasing unreasonably as the
size of the number to be factorized grows. This ability is astonishingly powerful.
As we have seen, the whole basis of the RSA cryptosystem - named for its inven-
tors, the computer scientists Ronald Rivest, Adi Shamir, and Leonard Adleman -
is the computational difficulty of factorizing large numbers. For example, in
1994, the 129-digit number known as RSA-129 required eight months to factor-
ize, using more than 1,600 computers (
Fig. 15.17
). If we could build a quantum
computer that was roughly the same speed as just one of the computers used in
this trial, Shor's algorithm could factorize RSA-129 in less than ten seconds. For
this reason alone, many government agencies around the world are now fund-
ing attempts to build a quantum computer.
The computer scientist Lov Grover discovered another interesting class of
algorithms in 1997. Grover's quantum search algorithm showed that a quan-
tum computer could greatly increase the speed of searching a database. An
example would be trying to find the name of a person in a telephone directory
if you only know their telephone number. For a database with N items, Grover's
Search WWH ::
Custom Search