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:

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

return to the contents page