Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 197

complexity is

e O (log n ) 3 (log log n ) 3 .

This method becomes substantially better than the previous ones as n increases. (In
practice, it becomes better when n reaches 100 to 150 decimal digits.)

As we will see in the next chapters, the ability to factorize large numbers enables
to break some cryptosystems. To monitor public progress in this area, factorization
challenges were issued by the company RSA Data Security. Every challenge is a large
number which is given a tag featuring its length. For instance, RSA155 is the following
155-decimal digits integer.

RSA155 = 10941738641570527421809707322040357612003732945449

20599091384213147634998428893478471799725789126733
2497625752899781833797076537244027146743531593354333897

.

This number was factorized on August 22, 1999 by a team of scientists from six different
countries, led by Herman te Riele of CWI (Amsterdam). They implemented a network
of computers that provided about 8000 mips

year (8000 millions of instructions per
second during one year), to discover that RSA155 is equal to

.

102639592829741105772054196573991675900716567808038066803341933521790711307779 ×

106603488380168454820927220360012878679207958575989291522270608237193062808643

which is a product of two prime numbers. A lot of efforts for a two-line conclusion!

7.2.7 Factorization Tomorrow

At this time, researchers are investigating a new computing model which no longer relies
on traditional microprocessors and memories. Instead, it relies on quantum mechanics .
This model or quantum computing assumes that the state of a computing machine
can be so isolated from an electromagnetic viewpoint that it can be in a quantum
state. Namely, instead of being on a well-defined state, it can be on a superposition of
(infinitely) many states associated with a complex weight. The probability that freezing
the machine ends up on a given state is the squared norm of the complex weight. Since
most people have been educated with well-defined deterministic state machines, this
model is clearly against the common intuition. Nevertheless, some experiments show
that such machines can be built, but the current state of the art limit them to a dozen
of quantum bits of memory. The question whether this model can scale or not is still
open today since the more quantum bits we have, the less stable states are.