CWI factors RSA-140 using number field sieve

 Amsterdam 02 Feb 99 A team lead by Dr. te Riele from CWI Amsterdam has for the first time in history broken an RSA-140 number with 140 digits, into its two Prime factors. RSA codes are used in real-life high-security applications. The smallest there being 155 digits, very close to the now proven to be unsafe RSA-140. It took 200 computers 11 weeks to break the code.

The amount of computer time spent on this new 140-digit NFS-record is prudently estimated to be equivalent to 2000 mips years. For the old 130-digit NFS-record, this effort is estimated to be 1000 mips years. For both numbers, lower "could-have-done-it-in" estimates, based on a better use of the lattice siever, are:500 mips years for RSA-130 and 1500 mips years for RSA-140.

Sieving was done on about 125 SGI and Sun workstations running at 175 MHz on average, and on about 60 PCs running at 300 MHz on average. The total amount of CPU-time spent on sieving was 8.9 CPU years. For the purpose of comparison, two sieving methods were used: lattice sieving and line sieving. For the lattice sieving, a rational factor base of 250 000 elements (the primes <= 3 497 867) and an algebraic factor base of 800 000 elements (ideals of norm <= 12 174 433) were chosen. For the line sieving, different factor base bounds were chosen, namely: a rational factor base consisting of the primes < 8 000 000 and an algebraic factor base with the primes < 16 777 215 = 2^24 - 1.

For both sieves the large prime bounds were: 500 000 000 for the rational primes and 1 000 000 000 for the algebraic primes. A total of 66 933 395 relations were generated, 55% of them with lattice sieving (L), 45% with line sieving (C). Among them, there were 10 327 897 duplicates, partially because of the simultaneous use of the two sievers.

Sieving started the day before Christmas 1998 and was completed one month later. The relations were collected at CWI and required 3.7 Gbytes of memory. The filtering of the data and the building of the matrix were carried out at CWI and took one calendar week. The resulting matrix had 4 671 181 rows and 4 704 451 columns, and weight 151 141 999 (32.36 nonzeros per row).

During February 1-2, 1999, four different square root jobs were started in parallel on four different 250 MHz processors of CWI's SGI Origin 2000, each handling one dependency. After 14.2 CPU hours, one of the four jobs stopped, giving the two prime factors of RSA-140. Two others also expired with the two prime factors after 19 CPU hours (due to different input parameter choices). Only one of the four jobs expired with the trivial factors.

The previous record was in April 1996 with the factoring of RSA-130.

The web site of the Group of Te Riele can be found at: web site

The number RSA-140 is taken from the RSA Challenge list www.rsa.com/rsalabs/html/factoring.html

Sandra Wermer