RSA200 factored

Numbercruncing cereals!

"We have factored RSA200 by GNFS. The factors are




We did lattice sieving for most special q between 3e8 and 11e8
using mainly factor base bounds of 3e8 on the algebraic side and 18e7 
the rational side. The bounds for large primes were 2^35. This produced
26e8 relations. Together with 5e7 relations from line sieving the total
yield was 27e8 relations. After removing duplicates 226e7 relations
remained. A filter job produced a matrix with 64e6 rows and columns,
having 11e9 non-zero entries. This was solved by Block-Wiedemann.

Sieving has been done on a variety of machines. We estimate that
lattice sieving would have taken 55 years on a single 2.2 GHz Opteron 
Note that this number could have been improved if instead of the PIII-
binary which we used for sieving, we had used a version of the
lattice-siever optimized for Opteron CPU's which we developed in the 
The matrix step was performed on a cluster of 80 2.2 GHz Opterons 
connected via a Gigabit network and took about 3 months.

We started sieving shortly before Christmas 2003 and continued until
October 2004. The matrix step began in December 2004.
Line sieving was done by P. Montgomery and H. te Riele at the CWI, by
F. Bahr and his family."