RSA-155
Factors:
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643
Date:    August 22, 1999
Method:  the General Number Field Sieve, 
         with a polynomial selection method of Brian Murphy 
         and Peter L. Montgomery,
         with lattice sieving (71%) and with line sieving (29%),
         and with Peter L. Montgomery's blocked Lanczos and 
         square root algorithms;
         both factors were proved to be prime with two different 
         primality proving algorithms
Time:    * Polynomial selection: 
         The polynomial selection took approximately 100 MIPS years, 
         equivalent to 0.40 CPU years on a 250 MHz processor. 
         The two polynomials

         F_1(x,y) =                  11 93771 38320     x^5
                             - 80 16893 72849 97582 y  *x^4
                          - 66269 85223 41185 74445 y^2*x^3
                  + 1 18168 48430 07952 18803 56852 y^3*x^2
                + 745 96615 80071 78644 39197 43056 y^4*x
           - 40 67984 35423 62159 36191 37084 05064 y^5

         F_2(x,y)  =  x - 3912 30797 21168 00077 13134 49081 y 

         were selected using procedures developed by Peter Montgomery
         and Brian Murphy for the factorisation of RSA-140.
         Better use was made of these procedures for the RSA-155 factorisation
         than for the RSA-140 factorisation. 
         The pair (F_1, F_2) has a yield of relations approximately 13.5 times 
         that of a random polynomial selection for RSA-155
         (the corresponding figure for the RSA-140 factorisation is
         approximately 8).

         The original polynomial selection code was ported by Arjen Lenstra
         to use his multiple precison arithmetic package LIP. 
         Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson
         ran polynomial searches for RSA-155. The above polynomial emerged 
         from Bruce Dodson's search.
         Calendar time for the polynomial selection was approximately nine 
         weeks.
         * Sieving: 35.7 CPU-years in total,
                    on about 160 175-400 MHz SGI and Sun workstations,
                    on 8 250 MHz SGI Origin 2000 processors,
                    on 120 300-450 MHz Pentium II PCs, and
                    on 4 500 MHz Digital/Compaq boxes;
                    this CPU-effort is estimated to be equivalent to 
                    approximately 8000 mips years;
                    calendar time for the sieving was 3.7 months; 
           124 722 179 relations were collected by eleven different sites,
           distributed as follows:
           (L: using lattice sieving code from Arjen K. Lenstra
            C: using line sieving code from CWI)
           20.1 % (3057 CPU days) Alec Muffett (L)
           17.5 % (2092) Paul Leyland (L,C)
           14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L)
           13.6 % (2222) Bruce Dodson (L,C)
           13.0 % (1801) Francois Morain and Gerard Guillerm (L,C)
            6.4 % (576) Joel Marchand (L,C)
            5.0 % (737) Arjen K. Lenstra (L)
            4.5 % (252) Paul Zimmermann (C) 
            4.0 % (366) Jeff Gilchrist (L)
            0.65 % (62) Karen Aardal (L)
            0.56 % (47) Chris and Craig Putnam (L)
         * Filtering the data and building the matrix took about a month
         * Matrix: 224 hours on one CPU of the Cray-C916 at SARA, Amsterdam;
                   the matrix had 6 699 191 rows and 6 711 336 columns,
                   and weight 417 132 631 (62.27 nonzeros per row);
                   calendar time: ten days
         * Square root:  Four jobs assigned one dependency each were run 
                         in parallel on separate 300 MHz R12000 processors
                         within a 24-processor SGI Origin 2000 at CWI.
                         One job found the factorisation after 39.4 CPU-hours, 
                         the other three jobs found the trivial factorization 
                         after 38.3, 41.9, and 61.6 CPU-hours
                         (different CPU times are due to the use of different
                         parameters in the four jobs).
         * The total calendar time for factoring RSA-155 was 5.2 months 
           (March 17 - August 22)
           (excluding polynomial generation time) 
           We could reduce this to one month sieving time and 
           one month processing time if we had more sievers and
           had more experience with matrix-generation strategies.
Names/   Herman J.J. te Riele (CWI Amsterdam, contact person)
sites:   Karen Aardal (Utrecht University, The Netherlands)
         Stefania Cavallar, Walter M. Lioen (CWI Amsterdam, The Netherlands)
         Bruce Dodson (Lehigh University, Bethlehem, PA, USA)
         Jeff Gilchrist (Entrust Technologies Ltd., Ottawa, Canada)
         Arjen K. Lenstra (Citibank, Parsippany, NJ, USA 
                           and Univ. of Sydney, Australia)
         Paul Leyland (Microsoft Research, Cambridge, UK)
         Joel Marchand (Ecole Polytechnique/CNRS, Palaiseau, France)
         Peter L. Montgomery (Microsoft Research, USA, and CWI)
         Francois Morain and Gerard Guillerm
              (Ecole Polytechnique, Palaiseau, France)
         Alec Muffett (Sun Microsystems Professional Services, Camberley, UK)
         Brian Murphy (The Australian National University, Canberra)
         Chris and Craig Putnam (USA)
         Paul Zimmermann (Inria Lorraine and Loria, Nancy, France) 
Address: (of contact person)
         Centre for Mathematics and Computer Science (CWI)
         Kruislaan 413, 1098 SJ  Amsterdam, The Netherlands
Email:   Herman.te.Riele@cwi.nl
Phone:   +31 20 5924106
Fax:     +31 20 5924199