Before you start...

[jasonp]

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 40-bit 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.

[Dubslow]

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):

Originally Posted by Paper

For a 768-bit RSA modulus 2 gigabytes of RAM per core works nicely, half of it still works too but is noticeably less efficient. For 1024 bits, 2 gigabytes of RAM per core would cut it too closely, but memories of 32 or 64 gigabytes per multi-core or multi-threaded processor (or even per mainboard) would work. These estimates take into account current processor and memory access speeds and are based on the fact that memory requirements grow roughly with the square root of the sieving time.

With a current desktop processor, 32 GiB is possible, giving 8 GiB per core, or 4 GiB per hyper-thread.

[Xyzzy]

Or "Operation Kibibit" )

That sounds pretty cool!

[Xyzzy]

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.

[Batalov]

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".

[jasonp]

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 factorization-related 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.

[retina]

So ... are we there yet?

I'll just grab my coat.

[jasonp]

Almost :)

[xilman]

Originally Posted by jasonp

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 factorization-related 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.

I've been working on the (generalized) Cullen & Woodall numbers for twenty years, and I'm far from the most obsessive factorer. Some people are into their fourth decade of factoring Cunningham numbers.

To make a concrete suggestion for RSA-1024, 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

[bsquared]

Originally Posted by jasonp

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?

There's also the significant probability of getting scooped to consider. The serious factoring groups around the world aren't necessarily regulars here (EPFL, NTT, Bonn, etc). I think it's likely they won't consider anyone else's efforts when they start this number yet they have the tools and resources to finish before others that may have started earlier.

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...

[only_human]

Originally Posted by Dubslow

Or "Operation Kibibit" )

Originally Posted by Xyzzy

That sounds pretty cool!

I like it
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)