Sun, 04 Apr 2004 02:45:51 +0900 (JST)

We are happy to announce the factorization of 2,1642M from the
Cunningham numbers.  We used SNFS to factor it.  The answer is:
  2,1642M =
  139838398039428521505951093426146672317977242051
61451430391332862456574221363722734055314582922181
82394011694786083970706758188061429005670580578819
43219670611471791456566889090642387438187278519182
88932286008372802624437907070565445887094633267201
=
75052937460116417664924678548932616036
64038102314712839047907776243712148179748450190533
. p160

FYI, from the Cunningham book, one can write:
  2^1642+1 = 2,1642L . 2,1642M
  2,1642M = 2^821 + 2^411 + 1

We made all programs for this factoring except that the number field
invariants are computed by PARI-GP.


=====Statistics=====
We used the abbreviation k as 10^3, M as 10^6, and G as 10^9.

[Polynomial selection]
Definition polynomial:
  x^6 + 2*x^3 + 2
and
  x - 2^137


[Sieving]
Environment:
  We mainly used 64 x Pentium 4 2.53GHz (FSB 533MHz) with 1GB RAM
without Hyperthreading technology which are located at University of
Electro-Communications, and Pentium 4 PCs with various frequencies at
Rikkyo University.  In total, we used about 100 PCs, but most PCs were
not always active in the sieving time.

Time: about 50 calendar days, which is scaled to about 8.2 Pentium 4
2.53GHz (FSB 533MHz) years.  Actually, we think that we do not need to
sieve entire area of our sieving region, but collecting entire
relations with slow network connection makes more relations before
filtering. :-)  We are estimating how many relations are sufficient to
factor the number.

<Line sieve>
We did not use line sieve.

<Lattice sieve>
sieve area: [-16k,16k)x[0,8k)
special q: only for rational side
 1.02M to 200M except 1.03M to 1.06M and 33.9M to 51.4M (about 10.2M 
primes)
factor base bound: about 0.95q for rational side, 100M for algebraic 
side
large prime bound: 4G for both sides
Yields: 558 455 641 relations
Note that 2 large primes were accepted at most for both side, and we
did not use free relations.


[Filtering]
Algorithm: partially implemented Cavallar algorithm
Environment: 32 x Pentium 4 2.53GHz (1GB) with 100baseT full-duplex
Most steps we only used 1, 2, 4, or 8 PCs.
Time: 8 calendar days (but PCs are idle in most times because of
waiting human operation)

  558 455 641 raw relations
  438 270 192 unique relations
  323 629 061 effective factor base
   25 247 811 relations after singleton and clique operation
   25 246 816 its effective factor base


[Linear algebra]
Input matrix: 7 429 778 x 7 429 097 (total weight 1 544 659 604)
Algorithm: block Lanczos with 128-bit block length
Environment: 16 x Pentium 4 (3.2GHz) with GbE full-duplex located at 
NTT
Time: 9.5 days (calendar days are about 15 because of hardware 
troubles)
We firstly removed heavy 96 rows from the matrix.  The weight was
reduced to 1 397 375 593.  After we got 128 block Lanczos solutions,
we recovered actual 33 solutions.  After got actual solutions, we
adjusted the unit with quadratic character for 32 solutions.  Finally,
we got 31 quadratic equations modulo 2,1642M.


[Square root]
Algorithm: Nguyen algorithm adjusted for parallel environment
Environment: 8 x Pentium 4 2.53GHz (average frequency) located at 
Rikkyo Univ
Time: about 4 hours for each solution
We found the factor by the 1st solution.


K.Aoki  Y.Kida  T.Shimoyama  Y.Sonoda  H.Ueda
Note that this factoring is partially supported by CRYPTREC project