On July 18, 1994, we completed the factorization of the 116-digit cofactor of the 117-digit 11887th partition number p(11887) into two primes of 46 and 70 digits using the general number field sieve factoring method (GNFS). This beats the 105-digit GNFS record that was set on June 13, 1994. More importantly, we spent less computer time on this factorization than we have spent in the past on comparable 116-digit factorizations using the Quadratic Sieve factoring method. p(11887) = 346846611533646507115441097715071440472547624162201648999031\ 960550372740453100547185861519429007908922786564243907189 = 23 * 3737871859084719251526725620648899205883329019 * 4034458115874869126233674445223891392270040052124810720248603067343497 Details on this factorization will be given in [DL]. See [LL] for a description of GNFS. We used the randomly selected (and not particularly good) polynomial 48256923796189830 X^5 + 35680803937265531 X^4 - 4656056181875120 X^3 - 59698831452621728 X^2 - 13442855525045260 X + 29654327274038354 and its root 49999999185476646567 modulo the 116-digit number to be factored. Sieving and trial division was done on workstations at Lehigh University and Bellcore in approximately 220 mips years. We used the implementation as described in [GLC] with a factor base size of 500,002 (100,001 primes on the rational side, 400,001 on the algebraic side) and a large prime bound of 2^30. It produced 61,849 full relations and 45,876,382 partial relations with at most four large primes. Number of | Number of large primes on algebraic side relations |------------------------------------------ ----------------| 0 1 2 | -------------------------------------- | 0 | 61,849 668,995 1,670,521 Number of large | | primes on | 1 | 466,728 5,038,434 12,521,329 rational side | | | 2 | 676,211 7,261,718 17,572,446 The partials led to 2,605,463 `cycles', where a cycle is a product of partial relations in which all large primes occur an even number of times. This was almost 6 times the number of cycles that we needed. There were on average 74.24 partials per cycle. Of the 45,876,382 partials 13,873,228 were actually useful, i.e., occurred in one or more cycles. The breakdown of these 13,873,228 partials: Number of | Number of large primes on algebraic side relations |------------------------------------------ ----------------| 0 1 2 | -------------------------------------- | 0 | 414,928 748,324 Number of large | | primes on | 1 | 301,013 2,029,137 3,645,018 rational side | | | 2 | 343,708 2,308,670 4,082,430 Restriction to the 6,174,157 partials with at most one large prime per side led to only 56,327 cycles, restriction to the 8,520,889 partials with at most two large primes in total led to only 93,328 cycles. Restriction to the cycles of length at most 23 led to 459,922 cycles for which we needed only 2,055,178 of all partials. Combined with the 61,849 fulls these sufficed. The average length of the 459,922 cycles was 12.34. The breakdown of the 2,055,178 partials that occurred in the 459,922 cycles of length at most 23: Number of | Number of large primes on algebraic side relations |------------------------------------------ ----------------| 0 1 2 | -------------------------------------- | 0 | 243,873 194,316 Number of large | | primes on | 1 | 191,757 549,493 346,063 rational side | | | 2 | 120,545 270,311 138,820 We had so many extra cycles for the following reason. At 28,243,831 partials only 224,217 were useful and generated 41,365 cycles, not even one tenth of what we needed. Just a little later, at 33,264,762 partials, we witnessed an interesting `cycle explosion': 3,486,661 usefuls and 317,862 cycles, which was suddenly quite close to what we needed. We decided to keep going for a while, to see if and how the explosion would continue. This led to 42,202,890 partials with 9,369,843 usefuls and 1,746,609 cycles of average length 92.93, but not sufficiently many short cycles to get a reasonably sparse matrix in the next step. After a bit more sieving we reached the point where the cycles of length at most 23 would suffice, which should be feasible for the matrix step. Combination of the 61,849 fulls and the 459,922 `short' cycles led to a not-so-sparse sparse 521,771 x 500,258 bit-matrix (including 256 columns for the quadratic signatures) with on average 277.17 one-bits per row. Using structured Gaussian elimination this matrix was reduced to a dense 274,696 x 274,496 bit-matrix. This took half an hour on a Sparc 10 workstation, plus a day and a half to build the almost 9 GByte dense matrix. This matrix was processed in 13 passes on Bellcore's 16K MasPar MP-1, using 52K per node and 6 CPU-days. The first dependency, consisting of 1,009,924 relations, was processed on an SGI workstation at the Centrum voor Wiskunde en Informatica in Amsterdam. After 36600 iterations, each of which reduced either the numerator or the denominator of the argument to the square root by about 10^130, the algebraic square root was reduced to the trivial sqrt(1). A sketch of the algorithm will soon appear in [PM93]. This took less than 2.5 CPU-days on a single MIPS R4400 processor. It resulted in the above factorization. Most steps of this computation can probably be improved considerably: better choice of polynomial(s), better choice of factor base size to take optimally advantage of the cycles explosion, and better matrix reduction (in particular [PM94] looks very promising). Bruce Dodson, Lehigh University, bad0@lehigh.edu Arjen K. Lenstra, Bellcore, lenstra@bellcore.com Peter L. Montgomery, CWI, pmontgom@cwi.nl [DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an explosive experiment, in preparation [GLC] R. Golliver, A.K. Lenstra, K.S. McCurley, Lattice sieving and trial division, Algorithmic number theory symposium, proceedings, Cornell, 1994 [LL] A.K. Lenstra, H.W. Lenstra, Jr., The development of the number field sieve, Lecture Notes in Math. 1554, Springer- Verlag, Berlin, 1993 [PM93] Peter L. Montgomery, Square roots of products of algebraic numbers, in Proceedings of Symposia in Applied Mathematics, Mathematics of Computation 1943-1993, Vancouver, 1993, Walter Gautschi, ed. [PM94] Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over GF(2), manuscript, July 1994