20120724, 01:30  #1 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Before you start...
This was written just after RSA768 was factored. I bring it up because there's a reason nobody has started thinking seriously about RSA1024.
Selecting a polynomial is something we can do now. Doing the sieving is something we cannot do now with current tools; think something like lasieve5e20 with three to five 40bit large primes. Just storing a factor base up to 2^34 would probably take 16GB. The public tools could not begin to handle postprocessing with 10^12 relations. Estimates for the size of the matrix range from 5x to 50x the size of the RSA768 matrix. If we had specialized software that squeezed down the sieving to a size that would fit commodity machines today at a significant performance cost, and got all the usual suspects to help, for years, then Moore's law combined with a fairly serious cluster could factor RSA1024. But make no mistake that it would be an extremely difficult, sustained worldwide effort. 
20120724, 02:05  #2  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
So we don't have the software for sieving or LA?
And on hardware, there might be a memory issue for the hypothetical siever, but given the software, the LA would be doable on a large (huge) cluster. Sound about right? (@Xyzzy: Perhaps "Operation Kilobit"? Or "Operation Kibibit" ) Edit: That paper suggests that 32 GiB would be a doable (probably not optimal) amount of memory required for a quad core (emphasis mine): Quote:
Last fiddled with by Dubslow on 20120724 at 02:14 

20120724, 02:34  #4 
Aug 2002
2·3·5·277 Posts 
Just a thought: The impossible is impossible until it is done.
We're not saying that the task is efficient, given that in five years our cell phones will be more powerful than our computers today, but we are saying it might be fun to try. This forum has a lot of resources. If we all kick in a core we could do something interesting. Or not. But the learning will be valuable. We are particularly interested in the discussion of how to attack the challenge. We have some pretty smart people here. Why don't you all start chatting here and those of us who are less developed intellectually can listen in and learn. 
20120724, 02:45  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010101011100_{2} Posts 
Hodja Nasreddin once said "I am just as strong as I was in my youth", and when asked how did he know that, replied: "See this stone? I couldn't lift it then and I cannot lift it now".

20120724, 12:24  #6 
Tribal Bullet
Oct 2004
3×1,181 Posts 
I never said it would be impossible. I just think everybody needs to think hard about the possibility of this project lasting long enough to exceed your interest in getting it done. What are you working on now in your spare time that you started five years ago? One year ago? Does stuff you thought was really cool one year ago look lame and boring now?
I won't have this problem, I started factorizationrelated programming in 2003 and think it's a nice excuse to learn about database coding. But many others will be in danger of putting in some token effort and ending up feeling they wasted their time. 
20120724, 12:55  #7 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
14211_{8} Posts 
What is the ETA please?
So ... are we there yet?
I'll just grab my coat. 
20120724, 12:58  #8 
Tribal Bullet
Oct 2004
3×1,181 Posts 
Almost :)

20120724, 13:11  #9  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2·5,477 Posts 
Quote:
To make a concrete suggestion for RSA1024, any initial effort should be placed in finding good polynomials. Such need to be found before productive sieving can take place. Polynomial searching is also something which can be done with yesterday's technology, unlike the sieving. While the search is proceeding (I estimate a few thousand core years would suffice) serious work can be done on how to implement the subsequent stages assuming availability of hardware which is plausibly in mass production in, say, five years time. But, please, don't anyone be under any illusions. Factoring a kilobit integer before 2020 will be phenomenally difficult. Paul 

20120724, 13:43  #10  
"Ben"
Feb 2007
2·1,789 Posts 
Quote:
Polynomial selection is the only thing that makes sense at this point. If a good enough one is found there is a chance that the folks that can actually finish the factorization will use it. But there is a greater chance that they will find something better on their own and our contribution will go unused... Last fiddled with by bsquared on 20120724 at 14:10 

20120724, 14:53  #11  
"Gang aft agley"
Sep 2002
EAA_{16} Posts 
Quote:
Here is the link to it Kibibit : http://en.wikipedia.org/wiki/Kibibit The link that Dubslow provided to Kibibyte could point to Kibibit as a see also reference (but doesn't as yet). Mebee I shouda look at modifying it. The Talk page for Kibibit asks "Where is the term "Kibibit" used?" Ha! I say, we shall soon see. (I deleted this message and then reinstated it. I mistakenly thought that I had put it in the wrong thread) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where should I start?  christian_  Information & Answers  9  20160122 19:28 
Where to start  Jellyfish420  Homework Help  46  20130206 13:51 
How to start?  Thomas11  Lone Mersenne Hunters  29  20081221 13:47 
how to start with P1?  ValerieVonck  Marin's Mersennearies  8  20060429 22:21 
How to start?  OmbooHankvald  Factoring  15  20050903 13:42 