CWI factors Giant Number in Record-Time
by Henk Nieland
On Wednesday, September 3, one of the several hundred computers at CWI yielded the two prime factors of the 180-digit number below, also written as (12167+1)/13. The factors were found after only twelve days of computation on 85 SGI/Cray computers at CWI. One special step in the computation, requiring huge memory space, was carried out at the Amsterdam Academic Computer Centre SARA.
The 180-digit number is the largest factored so far with the method employed here the Special Number Field Sieve (SNFS). The previous record (see: http://www.loria.fr/~zimmerma/records/), the factoring of a 167-digit number, was established last February by an international group of researchers who joined efforts through Internet. However, this job still required two months of computing time. In establishing the new record, CWI only used in-house resources. The record time - a speed-up with a factor five compared to the previous record - was due to recent software improvements by CWI researchers who moreover used faster computers than their predecessors.
The used code was originally developed at Oregon State University and by the Dutch mathematician Arjen Lenstra (now at Citibank, New York). During the last few years CWI has continually improved this code, leading to several world records in this research field.The American company Microsoft will shortly acquire the right to use this code, in order to become more familiar with the newest factoring technologies. With a related method, the General Number Field Sieve, the reliability of widely used cryptographic codes is tested.
Herman te Riele - CWI
Tel: +31 20 592 4106