Factoring Record starts Attack on RSA Code
by Henk Nieland
A 186-digit number was factored at CWI early September. This number,
compactly written as 3263341 - 1, was factored with the ‘Special
Number Field Sieve’, a method particularly suited to numbers of
this form.
The previous factoring record with this method, a 181-digit number,
was realized about one year ago also at CWI. Although apparently
not a spectacular progress, the acquired experience enables CWI
researchers Stefania Cavallar, Peter Montgomery (visitor from
the USA) and Herman te Riele to attack now a 512-bit RSA key -
the present most prominent challenge in this field - using the
still more powerful General Number Field Sieve method. This will
be done in cooperation with Microsoft and a few other institutions
disposing of abundant computing power. The RSA cryptosystem, still
considered as virtually uncrackable, is based on the difficulty
to factor certain large numbers. The researchers expect to finish
the job still in this millennium.
The factoring was completed within one and a half month using
88 SGI/Cray computers at CWI and the Cray C90 supercomputer at
the Academic Computing Centre SARA. The factored number was not
just another toy for CWI’s number addicts. Last year Warren D.
Smith of NEC Research Institute in Princeton asked CWI - a world
leader in this field - to factor this number for him. At NEC Research
one is interested in fast and reliable algorithms generating random
number sets which are applied, eg, in physics (experiment simulation)
and the financial world (assessing the value of investment portfolios).
Testing the quality of certain random number generators requires
the knowledge of the prime factors of numbers having the form
of the number now factored at CWI.
More information at http://dbs.cwi.nl/cwwwi/owa/cwwwi.print_projects?ID=12
Please contact:
Herman te Riele - CWI
Tel: +31 20 592 4106
E-mail: Herman.te.Riele@cwi.nl
