mersenneforum.org - Factorization of a 768-bit RSA modulus

We are pleased to announce the factorization of RSA768, the
following 768-bit, 232-digit number from RSA's challenge list:

12301866845301177551304949583849627207728535695953347921973224521517264005
07263657518745202199786469389956474942774063845925192557326303453731548268
50791702612214291346167042921431160222124047927473779408066535141959745985
6902143413.

The factorization, found using the Number Field Sieve (NFS), is:

3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489
*
3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917

Both factors have 384 bits and 116 digits. Referring to the smallest one
as p and its cofactor as q, we have the following prime factorizations:

p-1 = 2^8 * 11^2 * 13 * 7193 * 160378082551 * 7721565388263419219 *
111103163449484882484711393053 * p47
p+1 = 2 * 3 * 5 * 31932122749553372262005491861630345183416467 * p71
q-1 = 2^2 * 359 * p113
q+1 = 2 * 3 * 23 * 41 * 47 * 239875144072757917901 * p90

where pk denotes a k-digit prime number.

=====Paper=====
A paper describing the details of this factorization effort can be found
on [url]http://eprint.iacr.org/2010/006.pdf[/url] and on [url]http://lacal.epfl.ch/[/url]

=====Statistics=====
We use the abbreviation M for 10^6, and G for 10^9.
If a processor is mentioned without its number of cores only one
core was used. The clock rate of the AMD64 processors referred to is 2.2GHz.

[ECM]
For obvious reasons we did not do any ECM before starting the NFS
attempt. But at CWI (Centrum Wiskunde en Informatica, Amsterdam)
some ECM runs were done while the sieving was already underway.
Much earlier, when a prize was still offered for the factorization,
bountyhunters tried to factor RSA-768 using ECM and trial division.
All these attempts were unsuccessful.

[Polynomial selection]
In summer 2005 roughly 20 core years were spent on polynomial
selection at the BSI (Bundesamt für Sicherheit in der Informationstechnik,
Bonn) producing three polynomial pairs of roughly the same quality.
We used the Montgomery-Murphy method as improved by Thorsten Kleinjung.
Before entering the sieving phase we spent another 20 core years
in the beginning of 2007 at EPFL (École Polytechnique Fédérale de Lausanne,
Lausanne). No better polynomial pairs were found, but several of comparable
quality. We chose one of the three polynomial pairs of the first run:
algebraic side:
f(x) = 265482057982680 * x^6
+ 1276509360768321888 * x^5
- 5006815697800138351796828 * x^4
- 46477854471727854271772677450 * x^3
+ 6525437261935989397109667371894785 * x^2
- 18185779352088594356726018862434803054 * x
- 277565266791543881995216199713801103343120
rational side:
g(x) = 34661003550492501851445829 * x
- 1291187456580021223163547791574810881

[Sieving]
We started sieving in August 2007 and stopped in April 2009.

Environment:
We used various PCs and clusters at BSI, CWI, EPFL, INRIA (Institut
National de Recherche en Informatique et en Automatique, France),
NTT (Nippon Telegraph & Telephone, Japan), the University of Bonn,
EGEE (Enabling Grids for E-sciencE), AC3 (The Australian Centre for
Advanced Computing and Communications), and PCs in the United Kingdom.

Time:
Total sieving time is scaled to about 1500 AMD64 years.

We used only lattice sieving with special-q on the algebraic side.
Special-q:
most of 450M < q < 11100M (about 480M prime,root pairs) and
some q below 450M
Factor base bounds:
Depending on the memory available per job we used:
1GB: 450M on algebraic side, 100M on rational side
2GB: 1100M on algebraic side, 200M on rational side
for special-q below 450M a smaller algebraic factor base bound
was used
Large primes:
We accepted large primes up to 2^40, but the parameters were
optimised for large primes up to 2^37. Most jobs attempted to
split cofactors up to 2^140 on the algebraic side and 2^110
on the rational side, only considering the most promising
candidates.
Sieve area:
2^16 * 2^15
Yield:
64 334 489 730 relations
(38% INRIA, 30% EPFL, 15% NTT, 8% Bonn, 3.5% CWI, 5.5% others)

[Removal of duplicates and singletons, clique algorithm and filtering]
Environment:
This was done at EPFL on an eight-core machine with 10TB hard disk
space and on a cluster.
Time:
Scaled to less than 6 Core2 [2.66GHz] months.
Uniqueness step:
less than 10 days on a Core2 [2.66GHz] with 10 1TB hard disks
(most of this was done during the sieving phase)
64 334 489 730 raw relations from sieve
17 629 469 788 duplicates (27.4%)
46 705 019 942 unique relations (+57 223 462 free relations)
Removing singletons and clique algorithm:
less than 10 days on a Core2 [2.66GHz] with 10 1TB hard disks
2 458 287 361 relations
1 697 618 199 prime ideals
Filtering:
less than 2 days on up to 37 nodes of dual quad-core Core2 [2.66GHz]
(only one core per node used) produced the matrix below.

[Linear algebra]
Input matrix:
192 796 550 * 192 795 550 (total weight 27 797 115 920)
Algorithm:
block Wiedemann with block width 8*64
Environment:
- 110 * Pentium D [3.0GHz], Gb Ethernet, located at NTT,
- 56 * dual hex-core AMD64 Infiniband, located at EPFL,
- several ALADDIN-G5K clusters in France, with the choice
of clusters taking part in the computation adapted to
the available resources.
Time:
Scaled to 392 days on 12 * dual hex-core AMD64 = 155 core years
(where 155 approximates 12 * 12 * 392 / 365).

Calendar time for block Wiedemann was 119 days. In the first stage
of the computation (60% of the run time) up to 8 independent jobs
were done in parallel, in the last stage (after Berlekamp-Massey)
we ran as many jobs as possible in parallel.
Finally, we got 512 solutions which gave via quadratic character
tests 460 true solutions.

[Square root]
Algorithm:
Montgomery algorithm
Time and Environment:
2 hours for preparing data for 8 solutions (using the hard disk
and one core on each of 12 dual hex-core AMD64)
1.7 hours per solution (dual hex-core AMD64)
On December 12, 2009, we found the factors at the first solution.
A few minutes later four of the other seven jobs produced the
factorization as well.

Thorsten Kleinjung (1),
Kazumaro Aoki (2), Jens Franke (3), Arjen K. Lenstra (1), Emmanuel Thomé (4),
Joppe W. Bos (1), Pierrick Gaudry (4), Alexander Kruppa (4),
Peter L. Montgomery (5,6), Dag Arne Osvik (1), Herman te Riele (6),
Andrey Timofeev (6), and Paul Zimmermann (4)

1: EPFL; 2: NTT; 3: Bonn University; 4: INRIA; 5: MS Research; 6: CWI