AMSTERDAM, June 13, 1994.
A team of researchers from Amsterdam and Oregon have factored the 162-digit Cunningham number (12^151 - 1)/11 using the Special Number Field Sieve (SNFS). This team also factored a 105-digit cofactor of 3^367 - 1 using the General Number Field Sieve (GNFS), These beat the prior records of 158 digits (SNFS) and 75 digits (GNFS). The Amsterdam group also factored the 123-digit cofactor of the Most Wanted number 2^511 - 1 using SNFS.
The team members are
Centrum voor Wiskunde en Informatica (CWI),
Amsterdam, The Netherlands
Henk Boender Marije Huizing Walter Lioen
Peter Montgomery Herman te Riele Dik Winter
Oregon State University (OSU), Corvallis, Oregon, USA
Peter Montgomery Robby Robson Russell Ruby
Reed College, Portland, Oregon, USA
Joe Buhler Scott Huddleston
The 162-digit number is:
82 2196205286 5970195266 0120743076 1004273909 \
2435707339 6551677033 9373353207 4305023580 2427303275 6332005408 \
0668946066 9679221954 5093967127 3308456244 6289606063 0268212317
Its factors have 44 and 119 digits:
1653 7237851564 6889242614 0704164885 3990657743
497178678 0032337881 8763399005 9600164874 7659834953 9211569747 \
0057591532 2824191116 7043200927 0168842857 3103024883 1349126419
The 105-digit cofactor of 3^367 - 1 is
75870 1086707710 3419834518 9863846063 0208179089 \
1150247368 3674638356 7258455011 6888623834 4212966512 3030350997
Its factors have 52 and 54 digits:
15 1149525784 0070716998 8656940229 3793503992 8231350493
5019 5399738924 4528404247 9062790906 5410546896 2124251929
The 123-digit cofactor of 2^511 - 1 is
367 3961631816 9636306645 5843146059 9500161446 5522848532 4618588701 \
6494955401 1537804299 8485594889 1610390189 8798647139 0715399801
Its factors have 57 and 67 digits:
1447809 7418708626 0903935034 7614137456 436365782 90924150417
2537599 7450255191 3415676116 4267591913 5218355355 292247255 92538658153
The Number Field Sieve algorithm has four main phases: polynomial selection, sieving, linear algebra, and square root.
For (12^151 - 1)/11, the researchers chose the polynomials 12 X^5 - 1 and X - 12^30, with common root 12^30. The sieving took eight weeks during April-June, 1993, using 30 SPARC workstations in the OSU Mathematics Department. They gathered 8.98 million relations with large prime bound 100 million. These were used to construct a sparse 828,077 x 833,017 matrix with 26,886,496 nonzero entries. Using a novel Block Lanczos algorithm, the linear algebra took 3.4 hours on one CRAY C90 processor at the Academic Computing Center Amsterdam (SARA). The square root code uses another novel algorithm and took 10.5 hours per dependency, using one processor on an SGI Challenge at CWI. The factors were found on the second dependency.
For the cofactor of 3^367 - 1, the researchers used two quadratics:
342910527737 * X^2 + 86817069333519465483641612 * X
+ 540759062604782971357139536186424874771
and
1242060255079 * X^2 - 913049273181768816962553218 * X
+ 129128767300065233631168229536267982420800.
The resultant of these polynomials is nine times the C105. The sieving took four weeks during March-April, 1993, using 40 workstations in the Forest Science, Mathematics, and Statistics Departments at OSU. They gathered 3.59 million relations with large prime bound 30 million. It took 7.3 CRAY C90 hours to process the 1,284,719 x 1,294,861 matrix with 38,928,220 nonzero entries. The square root took 4.8 SGI Challenge hours per dependency. The factors were found on the first dependency.
The factorization of 2^511 - 1 used only SGI workstations at CWI. Sieving took 700 workstation-hours in May, 1994 using the polynomials X^6 - 10 * X^4 + 24 * X^2 - 8 and 2^36 * X - (2^73 + 1). Block Lanczos on the 430018 x 439058 matrix (total weight 13201980) took 97 hours on one processor of the SGI Challenge in 32--bit mode. The square root code took 12 hours per dependency on that machine. The factors were found on the first dependency.
The Oregon work was partially funded by a grant from the National Science Foundation. The Amsterdam work was partially funded by the Stieltjes Institute for Mathematics, Leiden. Funding for the Cray C90 time was provided by the Dutch National Computing Facilities Foundation NCF. The square root code uses the public domain PARI-GP library, developed at University of Bordeaux, France. Andrew Odlyzko of AT&T Bell Labs verified that the factors are indeed prime, using the APR test.
Peter L. Montgomery pmontgom@cwi.nl