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.
1286248074529200641089027285847866504705224464171357804194346814698101043793
0160098645877829367241942440036761175181846713094902521848685430625024876210
4794478806532579114244394693
(180 digits)
=
788539152479959923583473870729725158796647538883718863262181413347391236469
(75 digits)
x
1631178452565029206875585436566970202474113644621203858931609458045532501874
72604743326476435522680378897
(105 digits)
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.
Please contact:
Herman te Riele - CWI
Tel: +31 20 592 4106
E-mail: Herman.te.Riele@cwi.nl