View Single Post
Old 2010-11-08, 17:53   #1
poily
 
Nov 2010

2×52 Posts
Default RSA-190 factored

We are happy to report that after almost a half a year on November 8th, 2010 we finally got the factorization of the RSA-190 as follows
Code:
1907556405060696491061450432646028861081179759533184460647975622318915025587184175754054976155121593293492260464152630093238509246603207417124726121580858185985938946945490481721756401423481 
=
31711952576901527094851712897404759298051473160294503277847619278327936427981256542415724309619 
x
60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899
The job was done by I.Popovyan from MSU, Russia and A. Timofeev from CWI, Netherlands and took a few months of a pure computer time on various parallel systems in both MSU and CWI. The report is coming soon, here we just want to present a few details on the factoring process.

We used a polynomial
Code:
skew: 1.89723e+06
c5: 40208599020
c4: -1373979915646426
c3: -18783091380980602091391
c2: 32414999912320727344430346523
c1: -375830488267489810578184841744243639
c0: 348578818479643113591848726218653819076813
Y1: 127570152207571988302487
Y0: -543540225411856459303967064165519554
with murphy_e = 1.740627e-14. The polynomial was found with our modified version of the pol51 from the GGNFS on 100 nodes of the MSU cluster 'Chebyshov' in a few days in May 2010.

The sieving was done with T.Kleinjung's lasieve5 mostly on the CWI resources and resulted in over than 1000M relations in about 3 months.

After about of a month of debugging the matrix building code we finally got a matrix of size 33M. The matrix was solved using our MPI implementation of the Montgomery block Lanzcos algorithm in 54 hrs on 900 nodes of the MSU cluster 'Lomonosov' and gave 33 dependencies. Our experiments with the native msieve Lanczos code showed about 80 hrs on 400 nodes of the same cluster.

The square root step took ~110 hrs and finished on the 5th dependency with the factorization above.

The tools used for the whole job were msieve, our matrix step program and modified GGNFS utilities. We thank all the GGNFS contributors for their effort and jasonp for the msieve and his consultations about the matrix building step.
poily is offline   Reply With Quote