Date: Sat, 19 Jan 2002 23:47:43 +0100
From: Jens Franke
Subject: 2.953+ c158

We have completed the factorization of 2.953+ by factoring the c158
divisor

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603

into the factors

3388495837466721394368393204672181522815830368604993048084925840555281177

and

11658823406671259903148376558383270818131012258146392600439520994131344334162924536139 ,

which are declared prime by PARI. Five small prime divisors of 2.953+ have
been known before. The three larger ones have been found by P. Zimmermann,
T. Granlund und R. Harley using the method elliptic curves.

Polynomial selection for the c158 followed the Montgomery-Murphy Method.
Using several days of calendar time on about 20 PCs, we selected the
polynomials

                    16915642778160*X^5
               -756958519686871038*X^4
          -13302674486415639704432*X^3
        89395931439544311110799193*X^2
     81521488422532239989865771400*X^1 
-664290154060829787211338433347600*X^0

and
   X-74760919650729255820151370977

Sieving took two months of calendar time and produced a total of 309088646
relations, 18104418 by the line siever and 290984228 by the lattice siever.
the line siever was run over the rectangle (-5e8,5e8)x(0,2e4), using a factor
base bound of 30e6 on the rational and 110e6 on the algebraic side. Lattice
sieving was done on most special q on the algebraic side between 24e6 and
118e6, with factor base bounds depending on the special q. For most lattice
siever jobs, the total factor base size was about 4 million and the size of the
sieving rectangle was 16kx8k. Sieving would have taken less than 52 months on a
single 800MHz Athlon CPU.

After removing 55054854 duplicates from the siever output, we had 254033792
relations. After the pruning step, we had 110636597 useful relations.
Together with 234044 free relations, they produced an excess of 21341117
over the extended factor base size. This pruning job took about an hour on
four PIII PCs with one GB of RAM memory, connected by Gigabit Ethernet.
The filter job took 24 hours on six similar PCs and produced a matrix
with 5792705 columns, 5792259 rows and 710232534 entries. The block Lanczos
algorithm produced 62 elements of the kernel of this matrix. This took two
weeks on the six PCs on which the filter job was run. Quadratic character
checks reduced the number of solutions to 22. Three square root jobs, using
Montgomery's algorithm, took 15-30 hours on three 950 GHz PIII PC, depending
on the choice of parameters. Only one of them terminated with the trivial
divisor of the c158.

About 2/3 of the siever output was produced at the scientific computing
department at the institute for applied mathematics at the University of Bonn.
The remaining 1/3 of the siever output was produced at the institute for
pure mathematics, or using private resources. All postprocessing jobs took
place on a LINUX cluster built by the scientific computing department.

F. Bahr
J. Franke
T. Kleinjung

PS. [from Jens Franke, 22 Jan 2002]
a) The large primes bound was 32 bits for all siever jobs.
b) We are indebted to the following colleagues at the Institute for Pure
Mathematics for providing access to their office PCs: W. Ballmann,
C. F. Bödigheimer, U. Hamenstädt, T. Hefer, I. Lieb, B. Löwe, W. Müller,
F. Pop, A. Pratoussevitch.
c) H. te Riele verified the primality of the factors using a primality test
program of Bosma and van der Hulst.