mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-01-08, 00:09   #34
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Quote:
Originally Posted by Andi47 View Post
I think so too, but how to FIND a sextic polynomial?
The same way you find degree-4 and degree-5; the algorithm is independent of the polynomial degree, even if the code is not :)

While finding degree 6 polynomials is possible now, searching the space for good degree 6 polynomials is turning out to be surprisingly difficult unless the space is forced to be extremely small.

Last fiddled with by jasonp on 2010-01-08 at 00:13
jasonp is offline   Reply With Quote
Old 2010-01-08, 01:37   #35
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

19×137 Posts
Default

I'm a bit late to the party, but congrats! NFS@Home is honored to have earned a reference in the paper.

Last fiddled with by frmky on 2010-01-08 at 01:37
frmky is offline   Reply With Quote
Old 2010-01-08, 02:07   #36
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Comment in an Ars Technica thread, on why it's silly to base encryption on prime numbers because you can tabulate them all:
Code:
That's basically what they did. Instead of finding and storing all the 
primes they found and stored the products of all the primes. This took 
them 1500 years of processor time and 5TB to store the resulting data, 
so it's not quite as easy as you make it sound.

Last fiddled with by jasonp on 2010-01-08 at 02:07
jasonp is offline   Reply With Quote
Old 2010-01-08, 02:35   #37
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

102410 Posts
Default

Quote:
Originally Posted by xilman View Post
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
The version currently attached to the above link, version 1.0, includes
this correction. A friendly ammendment, certainly. -BD
bdodson is offline   Reply With Quote
Old 2010-01-08, 05:29   #38
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

5×499 Posts
Default

I wonder if RSA will mention this on its website despite having discontinued the contest in 2007. RSA did announce the factorization of RSA-200 from the old contest that was also cancelled, so I'm pretty curious how this will go.

Last fiddled with by ixfd64 on 2010-01-08 at 05:31
ixfd64 is offline   Reply With Quote
Old 2010-01-08, 07:42   #39
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Would RSA-1024 need a septic polynomial if it were ever done by GNFS?
10metreh is offline   Reply With Quote
Old 2010-01-08, 07:44   #40
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111010010112 Posts
Default

Maybe

Last fiddled with by Batalov on 2010-01-08 at 08:13
Batalov is offline   Reply With Quote
Old 2010-01-08, 08:39   #41
thome
 
May 2009

2×11 Posts
Default

Quote:
Originally Posted by 10metreh View Post
if we have a degree 6 poyfinder and a block Wiedemann implementation; is there a chance that any of the software used could become available to the public?
The block wiedemann implementation in cado-nfs exists, with two major blockers though (which depend on the little time I can allocate to it):
- there's no real documentation on how to run it in an mpi environment (but it works -- it's a matter of writing up some doc, and finish writing one matrix preparation tool).
- the central matrix berlekamp-massey code needs to be rewritten entirely in order to handle problems of this size. This is not trivial. The code we used for the factorization is not distributed presently.

A block Lanczos using the mpi+pthreads matrix product from cado-nfs would not be terribly hard to write. Might happen not too far from now.

E.
thome is offline   Reply With Quote
Old 2010-01-08, 08:46   #42
thome
 
May 2009

2×11 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Would RSA-1024 need a septic polynomial if it were ever done by GNFS?
The asymptotics tell you this (with bc -l):

n=2^768
e(l(3*l(n)/l(l(n)))/3)
6.33644328171517744982
n=2^1024
e(l(3*l(n)/l(l(n)))/3)
6.87076171913041326630

So 1024 nears the 6-7 border. I haven't spent a second of work on the topic, but it seems likely that degree 6 still wins for 1024. Kleinjung's paper at sharc06 suggest a polynomial of degree 6 as well, which is a mild indication that perhaps he also tried 7 and found out that 6 was better. anyway.

E.
thome is offline   Reply With Quote
Old 2010-01-08, 08:58   #43
thome
 
May 2009

2×11 Posts
Default

Quote:
Originally Posted by bsquared View Post
Fantastic! Cheers to all involved!

The paper mentions that a deliberate decision was made to not BOINCify or otherwise open up the sieving stage of the computation; mostly I gather from the desire to set a reasonably precise completion date and from a data management standpoint. I wonder how much could be gained if they opened it up, assuming the resources (administration/data management) were available? If not BOINC then at least a more widespread invitation to contribute. It seems like there would be lots of interest from the community to contribute to a record factorization, but maybe that's just the euphoria talking.

Anyway, congrats again!
Honestly, we were busy enough gathering data from the limited number of contributors. Much of the sieving effort was done from feb. 2008 to feb. 2009, and very importantly, it worked seamlessly with very little human interaction. If we had opened up the sieving stage to the crowd, I think we would have had a harder time supervising the bookkeeping.

So group efforts at this scale are not necessarily frowned upon, but that's really a management and supervision issue. Much easier to split into a small number of groups, rather than to have 1000+ contributors.

E.
thome is offline   Reply With Quote
Old 2010-01-08, 09:02   #44
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

24×13×29 Posts
Default

Quote:
Originally Posted by thome View Post
Honestly, we were busy enough gathering data from the limited number of contributors. Much of the sieving effort was done from feb. 2008 to feb. 2009, and very importantly, it worked seamlessly with very little human interaction. If we had opened up the sieving stage to the crowd, I think we would have had a harder time supervising the bookkeeping.

So group efforts at this scale are not necessarily frowned upon, but that's really a management and supervision issue. Much easier to split into a small number of groups, rather than to have 1000+ contributors.

E.
If you wanted more help at the cost of one more contributer i am sure you would find a volunteer on mersenneforum willing to organize help from mersenneforum+contacts(i.e. nfs@home etc.).
henryzz 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 05:09.


Tue Feb 7 05:09:51 UTC 2023 up 173 days, 2:38, 1 user, load averages: 2.13, 1.62, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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