From:   thor@MATH.UNI-BONN.DE
Subject: Factorization of the 1039th Mersenne number
Date: May 22, 2007 23:14:55 CEST
To:   NMBRTHRY@LISTSERV.NODAK.EDU
Reply-To:   thor@MATH.UNI-BONN.DE

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 va
lue.
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-923
M)
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