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