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
39505874583265144526419767800614481996020776460304936454139376
05157935562652945068360972784246821953509354430587049025199565
5335710209799226484977949442955603
into the factors
33884958374667213943683932046721815228158303686049930480849258
40555281177
and
11658823406671259903148376558383270818131012258146392600439520
994131344334162924536139 ,
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.
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.