[The E]

Ah, but remember this post:

#3 was changed to 250 million 200 character strings, apparently the point was that loading all of it into memory wouldn't be feasible.  We did get some solutions, a lot of brute force attempts but one guy in particular had some very interesting solutions for most of the problems.

I am not quite certain what cutting the problem up into discrete packages gives you, aside from the risk of never finding your duplicate.

Under the altered conditions, some measure must be taken to reduce memory usage. Portej's solution requires, in a pessimistic case, 9.87*10^282 bytes of memory, if not more due to oerhead. This is at best impractical.

I would really like to see the winning solution, though.

[chief1983]

Turns out the winning one might not have been optimal, however it was one of the best approaches to solving it with an algorithm that we saw.  I'll post the PDF from my laptop tomorrow probably.

Also, storing primes for cracking security would essentially be making a primes rainbow table.  Sure it's massive but it's what rainbow tables are all about.

[Spicious]

Also, storing primes for cracking security would essentially be making a primes rainbow table.  Sure it's massive but it's what rainbow tables are all about.

It's just say a few hundred orders of magnitude bigger.

You could always partition the words by starting letter, distribute each somewhere and repeat on subsequent letters until lists are small enough to work with in memory. Sounds like it could work nicely with a language like Erlang or Go.

[Bobboau]

I have a hard drive that can hold one trillion bytes of information, that should get me at least a decent sized list of primes. remember I don't need all primes up to N to factor N, I just need all primes up to sqrt(N), if I have a huge list of primes in a file on my hard drive, I just load one prime try to divide N with it and then move on until I find one that divides evenly.

[castor]

I am not quite certain what cutting the problem up into discrete packages gives you, aside from the risk of never finding your duplicate.

The point is that if there is a cheap way to tell which of the strings can't be duplicates in any case, we don't have to spend time comparing them against each other (other assumed benefits are the possibility for parallel processing and better cache utilization due to smaller working set). I admit it's not that easy in practice, since managing the memory usage would be quite tough even with the original setting. And if the input would need to be split to separate physical files it'd get slow as hell.  

edit: I quess you could also use an incremental version of the sorting idea; read the first n characters of every string, along with their offsets in the file. Sort, throw away unique lines. Append the next n characters to the remaining strings, sort again, discard unique strings. And so on..

[Spicious]

I have a hard drive that can hold one trillion bytes of information, that should get me at least a decent sized list of primes. remember I don't need all primes up to N to factor N, I just need all primes up to sqrt(N), if I have a huge list of primes in a file on my hard drive, I just load one prime try to divide N with it and then move on until I find one that divides evenly.

Keep in mind that for RSA these primes would be on the order of at least 2^512, if not 2^2048. Now, the number of primes less than n is ~n/log n - numbers that make a trillion puny by comparison.

[Bobboau]

well lets see here a 2^512 number would need, somewhere round 1.5*10^75 primes. so, yeah I guess your right.

[CP5670]

There is no efficient way to do problem 1 for huge numbers. It amounts to computing prime gaps, and as far as I know the only ways to do that are essentially brute force checks as people brought up earlier. There are some results giving bounds on prime gaps or describing them asymptotically, so you could use them to get a starting estimate or to eliminate some choices, but they are not sharp at all.

If you just want to find large primes, then that's comparatively easier.