One-Way Functions - Contemporary Cryptography - page 186

not factored until 1994 (with a distributed implementation of a variation of the QS
algorithm [9]). Just to give an impression of the size of such an integer, RSA-129
and its prime factors are reprinted here:

RSA − 129 = 1143816257578888676692357799761466120102182967212

4236256256184293570693524573389783059712356395870
5058989075147599290026879543541

= 3490529510847650949147849619903898133417764638493

387843990820577
3276913299326670954996198819083446141317764296799
2942539798288533

Today, the RSA Factoring Challenge is sponsored by RSA Laboratories to
learn more about the actual difficulty of factoring large integers of the type used in
the RSA public key cryptosystem. 5 In 1999, a group of researchers completed the
factorization of the 155-digit (512-bit) RSA Challenge Number, and in December
2003, researchers at the University of Bonn (Germany) completed the factorization
of the 174-digit (576-bit) RSA Challenge Number. The next numbers to factor (in
the RSA Factoring Challenge) are 640, 704, 768, 896, 1,024, 1,536, and 2,048 bits
long.

In the past, a couple of proposals have been made to use specific hardware
devices to speed up integer factoring algorithms. For example, TWINKLE is a
device that can be used to speed up the first step in the QS algorithm—that is, find
pairs ( x, y ) of distinct integers that satisfy equivalence (7.1) [10]. TWIRL is a more
recent proposal [11].

7.4 ALGORITHMS FOR COMPUTING DISCRETE LOGARITHMS

There are basically two categories of algorithms to solve the DLP (and to compute
discrete logarithms accordingly):

•

Algorithms that attempt to exploit special characteristics of the group in which
the DLP must be solved;

5 http://www.rsasecurity.com/rsalabs/challenges/factoring/