ERCIM News No.26 - July 1996 - CWI
Factoring Record through WWW
by Henk Nieland
RSA-130, a 130-digit number, has been factored in a world-wide
effort into two large, 65-digit prime numbers. This was achieved by combining
a relatively new mathematical method, the Number Field Sieve (NFS), with
the potential of World Wide Web for collecting the required data. Part of
the work was carried out by Marije Elkenbracht-Huizing at CWI and the University
of Leiden.
Further work along these lines might very well make the record short-lived,
a fact of some importance for the protection of confidential data streams
by RSA public key cryptographic techniques. The RSA-method, named after
its inventors Rivest, Shamir and Adleman, is based on the difficulty of
reconstructing from the product of two large prime numbers its constituent
factors. In practice, sometimes prime factors of about 80 digits are still
used.
Licences and products based on the RSA-method are sold by the American company
RSA Data Security, Inc. In order to keep track of the power of factoring
methods, the company has issued a list of prize-winning numbers to be factored,
starting with RSA-100 in 1991. The prize for RSA-130 was $13.000. Using
NFS, the fastest method so far for factoring such numbers, it would still
take 18 years on a modern PC with a 100 Mhz Pentium processor to factor
RSA-130. Since December 1995, every workstation owner with an Internet-connection
can contribute by collecting so-called relations. Thus Internet acts as
the world's largest parallel supercomputer (more information on: http://www.npac.syr.edu/factoring.html).
This project was initiated by the Dutch mathematician Arjen Lenstra (Bellcore,
USA). WWW-pages provide information, application forms, and instructions
on the installation of the program. Participants are automatically assigned
tasks and the discovered relations are also automatically sent to Arjen
Lenstra. CWI was a major participant: Elkenbracht-Huizing collected some
twenty million of the required seventy million relations, using sixty workstations'
spare time.
After the collection and a first selection the relations were sent to CWI.
Two difficulties had to be overcome, for which as yet no solutions had been
found: operations on a very large sparse matrix should be carried out very
fast, and as a final step the square root of a large algebraic number had
to be taken. Both problems were solved by Peter Montgomery (USA) during
a stay at CWI. The resulting program ran at the Amsterdam Computer Centre
SARA on a Cray C90 supercomputer, an indispensable tool because of its very
large memory.
Please contact:
Herman te Riele - CWI
Tel: +31 20 592 4106
E-mail: herman@cwi.nl
return to the contents page