Date: Mon, 02 May 2005 21:34:04 +0900 (JST)
To: ssw@cerias.purdue.edu, Paul.Zimmermann@loria.fr,
	paul@leyland.vispa.com, scott_contini@yahoo.com
Subject: factorization of 176-digit number
From: Kazumaro Aoki <maro@isl.ntt.co.jp>
X-UIDL: 1"J"!?^Q"!=_0!!<gC"!

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