mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-01-07, 10:17   #1
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default 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
akruppa is offline   Reply With Quote
Old 2010-01-07, 11:03   #2
pstach
 
Aug 2008

19 Posts
Default

Congrats on the great work guys.
pstach is offline   Reply With Quote
Old 2010-01-07, 11:05   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Terrific!
Thus, the next targets should only be

2^{1061}-1
\frac{2^{1123}+1}{3}
2^{1237}-1
2^{1277}-1
Raman is offline   Reply With Quote
Old 2010-01-07, 11:06   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

Superb!
fivemack is offline   Reply With Quote
Old 2010-01-07, 11:07   #5
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

Terrific!!

GNFS-232 with a SEXTIC??




Edit:

Quote:
Originally Posted by Raman View Post
Terrific!
Thus, the next targets should only be

2^{1061}-1
\frac{2^{1123}+1}{3}
2^{1237}-1
2^{1277}-1
add HP49.99 ;)

Last fiddled with by Andi47 on 2010-01-07 at 11:10
Andi47 is offline   Reply With Quote
Old 2010-01-07, 11:35   #6
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
Raman is offline   Reply With Quote
Old 2010-01-07, 12:16   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×7×827 Posts
Default

Quote:
Originally Posted by akruppa View Post

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 View Post
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
xilman is offline   Reply With Quote
Old 2010-01-07, 13:38   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

645410 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2010-01-07, 14:20   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·7·827 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
xilman is offline   Reply With Quote
Old 2010-01-07, 14:21   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-01-07, 14:22   #11
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

248710 Posts
Default

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
ixfd64 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modulus function on a linear convolution lukerichards Number Theory Discussion Group 4 2018-04-06 12:57
Extracting the Modulus from publickeyblob RSA 512 26B Homework Help 2 2014-11-30 07:31
It's possible to calculate an unknown RSA modulus? D2MAC Math 8 2010-12-26 16:32
Fixed leading bits in RSA modulus, vs NFS fgrieu Factoring 7 2009-09-23 11:45
Factoring with Highly Composite Modulus 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔