Date: Mon, 02 May 2005 21:34:04 +0900 (JST) From: Kazumaro Aoki We are pleased to announce the factorization of the 176-digit cofactor in 11,281+ (11^281+1) from the Cunningham numbers. We used GNFS to factor it. The factorization is: c176 in 11,281+ = 10098240736531334505088844 65819427259940099192936939289070048049173631682915 37078836750124948329070667886041202454205608993748 49022836745595410281489604207498450138102224691173 = p87 . p89 p87 = 8428398995380842661984668205419427509 43860088703946121840940131686719691460399191375953 p89 = 119812086993812743242137195174352093894 91006236671100986363096780488054684807819312870741 FYI, the partial factorization of 11,281+ was already done: 11,281+ = 2 * 2 * 3 * 2165143447416427 * 73717873044643423196357 * 47677949460728118782533826487424424473 * 46402408546690245400968842648859676155371 * c176 =====Statistics===== We used the abbreviation k as 10^3, M as 10^6, and G as 10^9. [Polynomial selection] The following polynomial pair was used: f(x) = 42465167160 * x^5 + 17988038900026354 * x^4 - 24485816371689913728521 * x^3 - 1668083704791996143020318484 * x^2 + 666155199819630813243886284231438 * x + 51503023516231281215723647769021985660 g(x) = 385940178780061631 * x - 750313181756151817259725353359779 The polynomial pair was generated by Kleinjung's polynomial selection program. We started the polynomial selection at February 5, 2005, and finished March 18, 2005. We only used a PC for the first 2 weeks, however, we used 52 PCs in 3 weeks that are located at Rikkyo University and NTT, and found the above polynomial pair March 8, 2005. The last week we only used 32 PCs for the polynomial selection but we did not find better polynomials. The most used PCs are based on Pentium 4 (Northwood) [3.2GHz] with hyperthreading technology. We estimated that about 3.5 Pentium 4 (Northwood) [3.2GHz] years were used. Note that we feel that we did not need to spend this long time. Before our sieving program was completed, we spent idle CPU cycles for polynomial selection. [Sieving] We started the sieving at March 16, 2005. PCs that joins the sieving were gradually increasing, and we can use dozens of PCs during University holidays. For small special-Q, the sieving program requires at most 512MB main RAM, it needs over 512MB for larger special-Q. We used our own sieving program, and its performance is increasing during sieving time because of optimizations. Environment: We used the following PCs located at Rikkyo University. 76 x Pentium III & 4 Athlon 64 1.0GHz-3.4GHz with 512MB-2GB RAM 148 x Pentium 4 2.6GHz(C) with 512MB RAM At NTT. 32 x Pentium 4 3.2GHz with 2GB RAM 28 x Pentium III & 4 & Opteron 1.0GHz-3.8GHz with 512MB-4GB RAM At Fujitsu Laboratories. 100 x Pentium III 1.0GHz*2 with 1GB RAM (Primergy Blade Server) 8 x Pentium III 1.4GHz*2 with 1.5GB RAM 7 x Pentium 4 3.8GHz with 2GB RAM In total, we used 399 PCs, but we could only use most PCs at weekend. Time: 27 calendar days, which is scaled to about 9.7 Pentium 4 3.2GHz years. In total, we used about 15.2 CPU year. We only used lattice sieving. sieve area: 512M points for each special-Q sieving rectangle is dependent on the special-Q special-Q: only for algebraic side. 100% of 30.5M-221.2M except 111.5M-113.4M (about 10.2M ideals) 83% of 28.8M-30.5M, 221.2M-227.0M (about 0.3M) factor base bound: about 0.95Q for algebraic side, 80M for algebraic side large prime bound: 4G for both sides Yields: 576 372 161 relations Note that 2 large primes were accepted at most for both sides, and we do not use any free relations. [Filtering] We started filtering job at April 7, 2005 for removing duplicates. We included relations until April 11, 2005 night. However, we continued sieving when we failed to make small matrix for linear algebra. We finished filtering job at April 16, 2005 noon. Algorithm: partially implemented Cavallar algorithm up to 21-way merge Environment: 32 x Pentium 4 3.2GHz (2GB RAM) with GbE full-duplex Most steps we only used 1, 2, or 9 PCs. Time: 9 calendar days (but actually we need about 2.5 days. The difference between calendar days and actual time mainly comes from waiting sieving output and resolving the bug in clique program.) 576 372 161 raw relations from sieve 455 989 949 unique relations (including 39 error relations) 328 707 916 effective factor base 27 220 932 relations after singleton and clique operation 27 219 940 its effective factor base [Linear algebra] Input matrix: 8 526 749 x 8 525 751 (total weight 1 707 545 745) Algorithm: block Lanczos with 256-bit block length Environment: 36 x Pentium 4 (2.8GHz-3.2GHz) with GbE full-duplex located at NTT Time: 5.3 days We firstly removed heavy 224 rows from the matrix. The weight was reduced to 1 394 050 132. We started block Lanczos program at April 16, 2005 and finished at April 21, 2005. After we got 256 block Lanczos solutions, we recovered actual 32 solutions. After got actual solutions, we adjusted the unit with quadratic characters. Finally, we got 24 quadratic equations modulo c176. [Square root] Algorithm: Nguyen algorithm adjusted for parallel environment Environment: 36 x Pentium 4 [2.8GHz-3.6GHz] located at NTT Time: about 1 hours for each solution The square root steps were performed midnight of April 21-22, 2005. We found the factor by the 4th solution. Acknowledgment. We thank Dr. Kleinjung that he kindly provided his polynomial selection program. K.Aoki Y.Kida T.Shimoyama H.Ueda