Date: Mon, 21 May 2007 09:47:35 +0200 (CEST)
From: Thorsten Kleinjung
Subject: M1039

We are pleased to announce the factorization of the 1039th Mersenne
number (2,1039- in the Cunningham table) by SNFS.
The factorization is:
2^1039-1 = p7 * p80 * p227 where
p7   = 5080711
p80  = 558536666199362912607492046583159449686465270184886376480100\
        52346319853288374753
p227 = 207581819464423827645704813703594695162939708007395209881208\
        387037927290903246793823431438841448348825340533447691122230\
        281583276965253760914101891052419938993341097116243589620659\
        72167481161749004803659735573409253205425523689
The factor 5080711 was already known.

=====Statistics=====
We use the abbreviation M as 10^6, and G as 10^9.
Timings are sometimes given in "CPU" years, where "CPU" is the name
of a processor, and sometimes in core years. A Pentium D has two cores,
a Dual Core2Duo four cores and all other processors mentioned have
one core.

[ECM]
Before factoring 2^1039-1 by SNFS, the potential candidates were tested
by ECM.  Several factors were found: B1=43e6, 2652 curves for c304 in
10,371- yielded p50 * c255, B1=43e6, 4094 curves for c306 in 2,2062M
yielded p47 * c259 and B1=43e6, 5490 curves for c307 in 2,2038M yielded
p49 * c259.  Next 10^311-1 was chosen as factoring candidate.  For this
number GMP-ECM 6.0 was used with parameters B1=850M and B2=default value.
Unfortunately, after trying 11784 curves for Step 1 and 11214 curves
for Step 2 a factor was found.  Many kind of PCs were used, and their
computational resources are scaled to about 7.91 Opteron 2.0GHz + 4GB
RAM years.  The result was published at the SCIS06 workshop in Japanese.

For 2^1039-1, Prime95 24.14 and GMP-ECM 6.0.1 were used.  1472 curves
with the combination of B1=850M and B2=12530G and 256599 curves with
the combination of B1=1100M and B2=2480G were tried.  The curves were
run on idle PCs in NTT labs, and in total about 127.5 Opteron 2.2GHz +
4GB RAM years were spent.  The probabilities to miss a small factor are
about 3.4% for 65 digits, 53.2% for 70 digits, 89.5% for 75 digits and
98.2% for 80 digits.

[Polynomial selection]
The following polynomial pair was used:
algebraic side:
     f(x) = 2 * x^6 - 1
rational side:
     g(x) = x - 2^173

[Sieving]
We spent 6 month calendar time for sieving.

Environment:
     We used various PCs and clusters at EPFL, NTT and the
     University of Bonn.

Time:
     Total sieving time is scaled to about 95 Pentium D [3.0GHz] years.
            (also scaled to about 100 Athlon64/Opteron [2.2GHz] years.)

We only used lattice sieving with special-Q on the rational side.
special-Q:
     most of 123M < Q < 911M (about 40M Qs)
     (in more detail: we sieved 100M-101M, 110M-915M and 920M-923M, but
     for the construction of the matrix the following regions were not
     used: 110M-123M, 892M-893M, 895M-896M, 909M-910M, 911M-915M, 920M-923M)
factor base bound:
     for Q < 300M: 300M on algebraic side, ca. 0.9 Q on rational side
     for Q > 300M: 300M on both sides
     for a small fraction of special-Q (850M-894M and 910M-925M) smaller
     factor base bounds (120M on both sides) were used
large primes:
     We accepted large primes up to 2^38, but the parameters were
     optimised for large primes up to 2^36. Most jobs attempted to
     split cofactors up to 2^105 (both sides), only doing the most
     promising candidates.
sieve area:
     2^16 * 2^15 for most special-Q
Yield:
     16 570 808 010 relations (84.1% NTT, 8.3% EPFL, 7.6% Bonn)

[Removal of duplicates and singletons, clique algorithm and filtering]
Environment:
     This was done at PCs and at the cluster at NTT.
Time:
     scaled to less than 2 Pentium D [3.0GHz] years
     or less than 7 calendar days (most of the uniqueness step was done
     during the sieving phase)
Uniqueness step:
     less than 10 days on one or two Opteron [2.0GHz] with 4GB
     16 570 808 010 raw relations from sieve
      2 748 064 961 duplicates (16.6%)
     13 822 743 049 unique relations
Removing singletons and clique algorithm:
     less than 4 days on up to 113 Pentium D [3.0GHz] (only one core used)
        755 746 955 relations
        594 150 319 prime ideals
Filtering:
     69 hours on 113 Pentium D [3.0GHz] (only one core used) produced
     the matrix below

[Linear algebra]
Input matrix:
     66 718 354 * 66 718 154 (total weight 9 538 688 635)
Algorithm:
     block Wiedemann with 4*64-bit block length
Environment:
     110 * Pentium D [3.0GHz], Gb Ethernet, located at NTT
     36 * Dual Core2Duo [2.66GHz], Gb Ethernet, located at EPFL
Time:
     scaled to 59 days on 110 * Pentium D [3.0GHz] = 36 core years
     or 162 days on 32 * Dual Core2Duo [2.66GHz] = 56 core years
     Note on core years: The speed of two jobs on the Pentium D
     cluster was about 1.5 times slower than one job and the load
     was about 1, which means that almost the same performance will
     probably made by a cluster with the same network but Pentium 4
     (3.0GHz Prescott) processors (essentially equivalent to a one
     core Pentium D).

Calendar time for block Wiedemann was 69 days. Most of the jobs were
done at NTT and EPFL in parallel. However, there were some periods
where no computation took place. Eliminating these periods the
computation could have been done in less than 59 days.
Finally, we got 50 solutions which gave via quadratic character
tests 47 true solutions.

[Square root]
Algorithm:
     Montgomery-Nguyen algorithm
Time and Environment:
     2 hours for preparing data for 4 solutions (Opteron [2.2GHz])
     + 1.8 hours per solution (Opteron [2.2GHz])
We found the factor at the 4th solution.

K.Aoki J.Franke T.Kleinjung A.K.Lenstra D.A.Osvik

 

 

 from:

http://www.loria.fr/~zimmerma/records/21039-