mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Kibibit

Reply
 
Thread Tools
Old 2012-07-24, 01:30   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default 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 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.
jasonp is offline   Reply With Quote
Old 2012-07-24, 02:05   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

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

Last fiddled with by Dubslow on 2012-07-24 at 02:14
Dubslow is offline   Reply With Quote
Old 2012-07-24, 02:30   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

11110011110112 Posts
Default

Quote:
Or "Operation Kibibit" )
That sounds pretty cool!
Xyzzy is offline   Reply With Quote
Old 2012-07-24, 02:34   #4
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

780310 Posts
Default

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.

Xyzzy is offline   Reply With Quote
Old 2012-07-24, 02:45   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011110001002 Posts
Default

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".
Batalov is offline   Reply With Quote
Old 2012-07-24, 12:24   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2012-07-24, 12:55   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32·653 Posts
Default What is the ETA please?

So ... are we there yet?

I'll just grab my coat.
retina is offline   Reply With Quote
Old 2012-07-24, 12:58   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Almost :)
jasonp is offline   Reply With Quote
Old 2012-07-24, 13:11   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

237178 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
xilman is offline   Reply With Quote
Old 2012-07-24, 13:43   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101000011012 Posts
Default

Quote:
Originally Posted by jasonp View Post
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...

Last fiddled with by bsquared on 2012-07-24 at 14:10
bsquared is offline   Reply With Quote
Old 2012-07-24, 14:53   #11
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

358110 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Or "Operation Kibibit" )
Quote:
Originally Posted by Xyzzy View Post
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)
only_human is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where should I start? christian_ Information & Answers 9 2016-01-22 19:28
Where to start Jellyfish420 Homework Help 46 2013-02-06 13:51
How to start? Thomas11 Lone Mersenne Hunters 29 2008-12-21 13:47
how to start with P-1? ValerieVonck Marin's Mersenne-aries 8 2006-04-29 22:21
How to start? OmbooHankvald Factoring 15 2005-09-03 13:42

All times are UTC. The time now is 16:14.

Tue Nov 24 16:14:53 UTC 2020 up 75 days, 13:25, 4 users, load averages: 1.54, 1.82, 1.76

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