mersenneforum.org Factorization of a 768-bit RSA modulus
 Register FAQ Search Today's Posts Mark Forums Read

 2010-01-07, 10:17 #1 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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 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
 2010-01-07, 11:03 #2 pstach   Aug 2008 19 Posts Congrats on the great work guys.
 2010-01-07, 11:05 #3 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts Terrific! Thus, the next targets should only be $2^{1061}-1$ $\frac{2^{1123}+1}{3}$ $2^{1237}-1$ $2^{1277}-1$
 2010-01-07, 11:06 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2·7·461 Posts Superb!
2010-01-07, 11:07   #5
Andi47

Oct 2004
Austria

2×17×73 Posts

Terrific!!

GNFS-232 with a SEXTIC??

Edit:

Quote:
 Originally Posted by Raman Terrific! Thus, the next targets should only be $2^{1061}-1$ $\frac{2^{1123}+1}{3}$ $2^{1237}-1$ $2^{1277}-1$

Last fiddled with by Andi47 on 2010-01-07 at 11:10

2010-01-07, 11:35   #6
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by akruppa 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.
If the factors were available on that day itself (12 December 2009 to be exact)
what were you all doing till now, why not report up the factors on that day itself
Thus, waiting for only to prepare up and then publish that paper? Today is already (7 January 2010)

Last fiddled with by Raman on 2010-01-07 at 11:36

2010-01-07, 12:16   #7
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×7×827 Posts

Quote:
 Originally Posted by akruppa 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.
Quote:
 Originally Posted by akruppa Yield: 64 334 489 730 relations (38% INRIA, 30% EPFL, 15% NTT, 8% Bonn, 3.5% CWI, 5.5% others)
I'm in the United Kingdom and I set in 443 023 790 relations but that number includes duplicates. 443 023 790 is 0.7 % of 64 334 489 730, so I guess I account for about one tenth of the "others".

Paul

 2010-01-07, 13:38 #8 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 645410 Posts I think it is distinctly inappropriate to suggest projects to or to complain about speed of publication from one of these major groups, and am minded to delete raman's posts from this thread. It is certainly conventional in a lot of scientific fields not to make announcements until the paper is ready (it would serve as a claim of priority, but there was nobody else working on RSA768), and a month from end of computation to getting the preprint out (note that the paper has two distinctly useful appendices, with a new trick for block-Wiedemann and a description of how the Kleinjung lasieve works) is very quick. xilman is properly credited in the full paper.
2010-01-07, 14:20   #9
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·7·827 Posts

Quote:
 Originally Posted by fivemack I think it is distinctly inappropriate to suggest projects to or to complain about speed of publication from one of these major groups, and am minded to delete raman's posts from this thread. It is certainly conventional in a lot of scientific fields not to make announcements until the paper is ready (it would serve as a claim of priority, but there was nobody else working on RSA768), and a month from end of computation to getting the preprint out (note that the paper has two distinctly useful appendices, with a new trick for block-Wiedemann and a description of how the Kleinjung lasieve works) is very quick. xilman is properly credited in the full paper.
Inappropriate, yes, and I suggest an apology would be appropriate. However, deleting the post is not the right response in my opinion.

I've now seen the full paper and will be mailing one of the authors with a suggestion for an amendment. Almost all my sieving was done on the teaching lab machines at the Genetics dept. of Cambridge University and I'd like that to be on record.

Paul

2010-01-07, 14:21   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

Quote:
 Originally Posted by fivemack I think it is distinctly inappropriate to suggest projects to or to complain about speed of publication from one of these major groups, and am minded to delete raman's posts from this thread. .
Applause!!!!!

Especially from someone who has not produced a single research result,
published a single paper, or implemented even a single relevant algorithm on
his own.

 2010-01-07, 14:22 #11 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 248710 Posts Congratulations! It's too bad RSA doesn't offer cash prizes for these factorizations anymore. Last fiddled with by ixfd64 on 2010-01-07 at 14:29

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Number Theory Discussion Group 4 2018-04-06 12:57 26B Homework Help 2 2014-11-30 07:31 D2MAC Math 8 2010-12-26 16:32 fgrieu Factoring 7 2009-09-23 11:45 mgb Math 3 2006-09-09 10:35

All times are UTC. The time now is 23:09.

Wed Nov 30 23:09:31 UTC 2022 up 104 days, 20:38, 0 users, load averages: 0.86, 0.97, 1.00