[crypto] 307 digit number factored

[R. Hirschfeld]

------- Start of forwarded message -------
Date:         Tue, 22 May 2007 17:14:55 -0400
From:         Thorsten_Kleinjung
Subject:      Factorization of the 1039th Mersenne number

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 = 55853666619936291260749204658315944968646527018488637648010052346319853288374753
p227 = 20758181946442382764570481370359469516293970800739520988120838703792729090324679382343143884144834882534053344769112223028158327696525376091410189105241993899334109711624358962065972167481161749004803659735573409253205425523689
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-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
------- End of forwarded message -------