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