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 http://eprint.iacr.org/2010/006.pdf and on http://lacal.epfl.ch/ =====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