VaKo Posted October 4, 2006 Share Posted October 4, 2006 Well, the only way we're going to do this is if we all mail someone a computer, and build a giant cluster. Quote Link to comment Share on other sites More sharing options...
pseudobreed Posted October 4, 2006 Share Posted October 4, 2006 It would be a great project, however... One you would need someone to delegate Two you would need some type of project management system. Three you would need this all to take place somehow in HL2DM I would not get intimidated by other schools/governments. Yeah, they have more people and better equipment, that does not always mean they come out with a better product/idea. A couple examples: Carl Hayden High School vs MIT Stanford University vs The Red Team in DARPA Quote Link to comment Share on other sites More sharing options...
Jester Posted October 4, 2006 Share Posted October 4, 2006 I played with this before but gave up because I was working on my own and :( extremely past the point of being impossible to do by myself. Cooper had the right idea there by creating like a rainbow table type thing with all the primes up to the number we are looking for. I actually had the code where we could split up the primes and everyone would then take a section and what not let me see if I can find it when I get home. I had the stats and everything setup so we could put together how much time it would take. then once we had a complete list of all the primes the work would be a lot simplier and then would have to be consentrated down to one machine. Anywho I will post again once I can find the code. :D Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 The moment before I passed out last night I had the idea of the rainbow tables (I knew I should have gotten up and posted about it before others). If you could generate all primes up the the digit length of the given semiprime, one could brute-force every possible combination between the two data sets and discard ones that have been tried. Yes, it would take a while to generate all of the prime numbers from 1 digit to 212 digits (or whatever number one goes after) but once completed, it shouldn't take that much longer to figure out which two prime numbers are factors of the semiprime. Next question would be, how many prime numbers are there in 1 to 212 digit-length numbers and how much storage space would this take up. Quote Link to comment Share on other sites More sharing options...
blizz Posted October 4, 2006 Share Posted October 4, 2006 likely alot of primes. and it would take too long to compute those. just too long Quote Link to comment Share on other sites More sharing options...
VaKo Posted October 4, 2006 Share Posted October 4, 2006 If they used 80 high end machines and it took then months with the RSA-640, then I can imagine the RSA-704 will take a year or more on the same kit. We have desktop PC's. Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 Found this, could be of use for anyone wanted to learn more about how this works or possibly considering take a stab at it. http://www.boo.net/~jasonp/qs.html Quote Link to comment Share on other sites More sharing options...
omega_ion Posted October 4, 2006 Share Posted October 4, 2006 If they used 80 high end machines and it took then months with the RSA-640, then I can imagine the RSA-704 will take a year or more on the same kit.We have desktop PC's. If we were evil people, we could create a worm that would create a zombie-web of computers being forced to compute RSA-704, but I doubt that's ethical. Quote Link to comment Share on other sites More sharing options...
jool Posted October 4, 2006 Share Posted October 4, 2006 I think some people here just don't appreciate the complexity of this kind of problem, mostly from a lack of experience with math like this it seems. If you don't even notice the difference between an actual algorithm and the big o for it this kind of thing might not be for you. If you did and also have a supercomputer in your basement it might be different. And about writing an GNFS for yourself the description on wikipedia seems to be as clear as they get. It's at least better than the one I had to code from. They also have links to open source implementations that you could run without much understanding. But without optimizing them for this specific task you haven't got a chance. GNFS on wikipedia Quote Link to comment Share on other sites More sharing options...
cooper Posted October 4, 2006 Share Posted October 4, 2006 Some interesting reading on primes. As a rough estimate, about 1 in 18 numbers in the number space 0 to 275 million are prime numbers. That becomes 1 in 23 for the number space 0 - 25 billion. To put it another way, when testing numbers for this algorithm, about 4% of the total keyspace is prime. 80% can be discarded trivially, but that leaves another 16% of pure fluff that you shouldn't waste your cycles on. The thing however is that 4% out of a keyspace of 200+ digits is more diskspace than can be sensibly kept, so I guess the rainbow tables thing is out on this one. Quote Link to comment Share on other sites More sharing options...
PoyBoy Posted October 4, 2006 Share Posted October 4, 2006 /raises hand Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 4, 2006 Author Share Posted October 4, 2006 I never said that was the algarithum, I said it was the big O for it. The porblem is that for GNFS to work you need a list of all primes up ot the bound. Pirme calculation thru direct search is easy ( I have code for it). HOwever, I do not have the lybrabrys to wor with numbers greater than 2^32-1 (32-bit P4) also, my algarithum uses a direct search prime test of for (form 3 to sqrt(number)+1 step 2) then with each number I do an if prime_to_test % (modulus) test_possible_factor==0 then its composite. There are inherntly faster primiality tests than a direct or brute force. If we generates all the primes, then yes you could just do a diret search. All GNSF does is lower the amount of numbers to test form the sqrt(number to factor) to much much less. We esencialy only need to get rid of as many composits as possible before even testing for primes. Then the algarithum can be semi-efficient. I really only need a larege number lybrary to do it. As for worms, I know a guy who knows a guy^6 that has a botnet. We all have "those guys" in our address book. We could easly get liek 5-6k computers on this, just need to write it. I really just need an effeicent prime test algarithum, and a way to work with numebrs larger than 32-bit. In java this is acomplished by storing the numbers as stirngs and parsing them in 32-bit chunks, there are lybrabrs for C++ that can do this though I haven't found any easy enough to use. Hak5 RSA@home might work. WE just need code, time and prossesors. As for splittting it up, you simply have person A do the first 20 million primes, B do the next and so on. Then you build it. THough, keep in mind that a list this large would be WAY WAY WAY WAY larger than any rainbow table know to man. Generating the list isn't the problem, its ust really how much time it takes. BUt transproting a list thas myabe up to 20 terabytes (ok Im over exadurating) isn't easy. Obviously you would split the list up into peaces, and ud dl them and modulus but still. This is like rainbow tables, just we have to write teh rainbowcrack Quote Link to comment Share on other sites More sharing options...
Garda Posted October 4, 2006 Share Posted October 4, 2006 The NSA has probably already done this and is just sitting around laughing at us...as they read these posts being intercepted by their echelon system. Yes they do read our messages, they do NOT have better things to spend their time on. And spektormax. PARAGRAPHS. Dude, just arbitrarily press enter every so often as you're writing your message if you can't manage anything else Quote Link to comment Share on other sites More sharing options...
cooper Posted October 5, 2006 Share Posted October 5, 2006 Oh, it's the library that's the problem? Gnu Multiple Precision Library. Presumably the fastest big number library on the planet. When I was using it, I did so through NTL. Someone else had already decided this one, so I don't know about the criteria that led to this decision, but it didn't appear to me to be a poor decision. Quote Link to comment Share on other sites More sharing options...
tabath Posted October 5, 2006 Share Posted October 5, 2006 For those with an interest in primes there is already a distributed project working on finding larger and larger (mersenne) primes. Google GIMPS . They have already got up to round about 9800000 digits long as of sep 11 2006 and are heading for the EFF prize of I think $100,000 for finding a 10 mill digit prime. I did a bit of number theory during my maths degree and found it very interesting but that was a while ago - one of my Professors specialised in it and that is the level of guy you really need if you are going to find any better way to compute this thing - otherwise you really need more distributed computers than hak5 could possibly get on to this task. Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 5, 2006 Author Share Posted October 5, 2006 well mersenn primes are very special caseses, so its very easy to calculate. ANd yes we need some hard core math to make it worth it Quote Link to comment Share on other sites More sharing options...
metatron Posted October 6, 2006 Share Posted October 6, 2006 Some interesting ideas, it’s not that hard to do, it just takes time. Quote Link to comment Share on other sites More sharing options...
PoyBoy Posted October 6, 2006 Share Posted October 6, 2006 Woot. If meta says itll work it will!!!!! Quote Link to comment Share on other sites More sharing options...
lightman Posted October 10, 2006 Share Posted October 10, 2006 Some interesting ideas, it’s not that hard to do, it just takes time. well, how long you guys think?, let's talk about a realistic approach, if we can use 10.000 AMD64-3000 computers, how long would it take?. I Bet that most of us has access to at least 10 computers like this that are idle most of the time, so only need 1000 of us to do it. am I talking nonsense? if the app to preform this can be paralelized in a way that doesn't require too much bandwidth between process, perhaps we can really do it. another issue would be storage, how big do you thing something like this will be?. even if we don't make it in time and don't get the money, such a sucess would be something really amazing!. Quote Link to comment Share on other sites More sharing options...
addisonzinser Posted October 10, 2006 Share Posted October 10, 2006 all you really need for this is get like 200 core 2 duo's and like 6 smart people. lol Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.