Date: Tue, 24 Jan 2006 16:05:56 +0900 (JST) Subject: SNFS274 From: Kazumaro Aoki Hello! Factoring people, (Sorry for omitting email addresses due to the privacy law) We are pleased to announce the factorization of the 274-digit(911-bit) number which is labeled as 6,353- in the Cunningham table. We used SNFS to factor it. The factorization is: c274 = (6^353-1)/5 = 97369150518441644256595898307653103810177469944544 60344424676734039701450849424662984652946941878917 94816051886144204066226423206167081784681898063663 68550930451357370697905234613513066631782316112426 01530501649312653193616879609578238789980474856787 874287635916569919566643 = p120 * p155 p120 = 13509526133011265183077504963559080738112103111138 27323183908467597440721656365429201433517381980576 36666351316191686483 p155 = 72074438111130193764393586402902539161389086709970 78170498495662717857340748450948116108762737328670 41786794660514517682420730722427836886613902736846 23521 =====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: algebraic side: f(x) = x^6 - 6 rational side: g(x) = x - 6^59 [Sieving] We started the sieving on September 10, 2005 and completed on November 16. For a small special-Q, the sieving program requires at most 512MB main RAM, it needs 1GB for a larger special-Q. Environment: We used many PentiumIII(1.0GHz) and Pentium4(2.6-3.4GHz) located at Rikkyo University, NTT and Fujitsu Laboratories. Time: Total sieving time is scaled to about 16.6 Pentium4(3.2GHz) years. (also scaled to about 17.3 Athlon64(2.0GHz) years.) We only used lattice sieving. special-Q: only for rational side. 5M < Q < 200M (about 10.7M Qs) factor base bound: about 0.95Q for rational side, 150M for algebraic side large prime bound: 16G for both sides (We set the parameters optimal for 16G and collected the relations with large primes up to 128G) sieve area: 512M points for small special-Q (about 4.9M Qs) 1G points for large special-Q (about 5.8M Qs) sieving rectangle form is dependent on the special-Q Yields: 2 497 019 540 relations Note: 2 large primes were accepted for both sides. [Filtering] Algorithm: partially implemented Cavallar algorithm up to 24-way merge Environment: We used various PCs for each filtering stage. 2 x Opteron 2.0GHz (4GB RAM) are used for the heaviest stage. Time: 14 days (without unused trials using different parameters) 2 497 019 540 raw relations from sieve (including 47 error relations) 2 208 187 490 unique relations 2 576 689 745 effective factor base 15 653 157 # of free relations 84 078 616 relations after singleton and clique operation 84 078 359 its effective factor base [Linear algebra] Input matrix: 19 591 108 x 19 590 832 (total weight 4 498 603 077) Algorithm: block Lanczos with 256-bit block length Environment: 25 x Pentium 4 (3.2GHz) with 2GB RAM and GbE full-duplex located at NTT Time: 34.64 days (without maintenance period) We firstly removed heavy 224 rows from the matrix. The weight was reduced to 3 938 362 368. We started block Lanczos program on December 5, 2005 and finished on January 19, 2006. After we got 256 block Lanczos solutions, we recovered actual 34 solutions. We then adjusted the unit parts of 32 solutions (subset of these 34 solutions) with the help of quadratic characters. Finally, we got 30 quadratic equations modulo c274. [Square root] Algorithm: Nguyen algorithm adjusted for parallel environment Time and Environment: 50 minutes (1 x Pentium 4 [3.6GHz] located at NTT) + 3.2 hours (25 x Pentium 4 [3.2GHz] located at NTT) We found the factor by the 1st solution on January 23, 2006. All programs were written by ourselves. K.Aoki Y.Kida T.Shimoyama H.Ueda