From herman Thu Apr 22 10:42:40 1999
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: 211-digit SNFS factorization
Status: R


----------------------------
211-digit SNFS factorization 
----------------------------

``The Cabal'' *) announces the completion on April 8, 1999
of the factorization with the Special Number Field Sieve (SNFS)
of the Cunningham number N = (10^211 - 1)/9 into two primes of 
93 and 118 digits, respectively. 
This establishes a new record for SNFS. It also establishes
a record for the largest penultimate prime factor ever found.
The previous SNFS record was the 186-digit number 32633^41 - 1
factored in September 1998 by a CWI group
(ftp://ftp.cwi.nl/pub/herman/SNFSrecords/SNFS-186). 

We used the polynomials

            f(X) = 10 X^6 -1
            g(X) = X - 10^35

with common root m = 10^35 (mod N).

The factor base bound was 2^24 both for f and g. The large prime
bounds were 600 and 500 million for f and g, respectively.

The sieving was done on about 125 SGI and Sun workstations running at
175 MHz on average, and on about 60 PCs running at 300 MHz on average.
It was started on February 4, 1999 and finished at the end of March 1999.
Total sieving time was 10.9 CPU years. For comparison, sieving for RSA140 
(ftp://ftp.cwi.nl/pub/herman/SNFSrecords/RSA-140) took 8.9 CPU years. 
As with RSA140, two sieving methods were used, viz., lattice sieving and 
line-by-line sieving.
For the lattice sieve the special q - primes were chosen from subintervals 
of [2^24, 10^8]. For the line sieve, the sieving region 0 < a < 6 million, 
|b| < 18 million was chosen.
 
A total of 56394064 relations were collected by various contributors 
according to the following table:

----------------------+--------------------+------------------------|
                  %   | lattice   %   CPU- | linebyline %    CPU-   |
                      | sieving       days |   sieving       days   |
----------------------+--------------------+------------------------|
Stefi Cavallar    8.7 |  4900438  8.7  756 |                        |
Bruce Dodson     22.4 |  6613515 11.7  389 |  6026521  10.7   334 1)|
Arjen Lenstra     9.4 |  5314891  9.4  319 |                        |
Paul Leyland     25.4 | 14309742 25.4  476 |                        |
Peter Montgomery 15.9 |                    |  8979310  15.9   183 2)|
Peter Montgomery 15.1 |                    |  8505108  15.1  1420 3)|
Paul Zimmermann   3.1 |  1744539  3.1   89 |                        |
----------------------+--------------------+------------------------|
                100.0 | 32883125 58.3 2029 | 23510939  41.7  1937   |
----------------------+--------------------+------------------------|
1) and 2) here, for the line-by-line sieving, a factor base bound of 
          40 million was used (rather than 2^24)
2)        on CWI's SGI Origin 2000 
3)        on SGI and Sun workstations at CWI

A filter program, in which ideals appearing up to five times were merged,
transformed the 56394064 relations into 4895741 relation sets
yielding a matrix with 4820249 rows and 4895741 columns with 234162626 1's,
i.e., an average of 48.6 1's per row.

The Block Lanczos program took 121 hours on the Cray C90 in order to 
find 64 dependencies. For comparison, the Block Lanczos run for RSA140
took 100 CPU hours on the Cray C90 for a matrix of comparable size,
namely 4671181 rows and 4704451 columns, but with a smaller density,
namely 32.3 1's per row.

The square root program, finally, needed 15.5 hours on one CPU of CWI's 
SGI Origin 2000, and three dependencies to find the two prime factors:

p1 = 692624557324389620662782322677336711138108482588281739734375\
     570506492391931849524636731866879 
     (93 decimal digits)

p2 = 160420403718189849284245217763423312082549489560444525405936\
     9227570068074354992595031636365651567169241873842145514809
     (118 decimal digits)

Primality of p1 and p2 was proved twice, viz. with help of the Jacobi sum
test program of H. Cohen, A.K. Lenstra and D.T. Winter, and with help of the
cyclotomy test program of Bosma and Van der Hulst. CPU time was only a few 
seconds.

Factorizations of p1-+1 and p2-+1:

p1-1=2.7.11.73.211.104121674194311581.p70
p1+1=256.3.5.23.47.191.1429.1907.351133.23083545197.
     1355216763137.7647041370665119.3816351055699890638466789845130863

p2-1=8.7.11.19.19.23.211.553549.25324026023.
     (the next p41 was found by Paul Leyland using ECMNET)
     20520646346002560283517813851387071577333.
     5167512574763221382378499730938591618625422936134521
p2+1=2.3.5.109.163.290588480202635737.p95

        We thank the Dutch National Computing Facilities Foundation NCF
for providing access to the Cray C90, and all those workstation and PC
owners for allowing us to use their idle evening, night and weekend cycles.
Arjen Lenstra acknowledges John Cannon and the University of Sydney 
for providing him access to some of their workstations.

The Cabal

(Stefania Cavallar, Bruce Dodson, Arjen Lenstra, Paul Leyland, 
Walter Lioen, Peter Montgomery, Herman te Riele, Paul Zimmermann)

*) Originally derived from persons and geographical names involved
   but also associated with ``Constantly Attempting to Break Any Length''.