4 ms·
Here's another approach: Let the compressed file contain a hash (say, SHA1) of the original file. The decompression program then generates random files of the
by splicer 14y ago
Here's another approach:
Let the compressed file contain a hash (say, SHA1) of the original file. The decompression program then generates random files of the chosen size. If a generated file's hash doesn't match the desired hash, delete it. Now run the program for a very long time. The program is likely to eventually reproduce the original file (along with a bunch of files that happen to have the same hash), and you win :)
- shubhamjain 14y agoWould complete in perhaps just a couple of billions of years. :)
- UnoriginalGuy 14y agoBut the rules didn't say the file had to be massive. You get to pick the size, so pick 100 Kb or similar. That would still take forever...
- deleted 14y ago[deleted]
- Beltiras 14y agoLet's say you have a file of size n and a hash of size log(n). This means you have n/log(n) collisions (matches). I made a similar suggestion on another HN thread linking that same story (I suggested using two radically different hashing functions, one hash result would not necessarily have an evenly distributed result from the other hashing function when you vary the plaintext). Even while posting I thought that I must be wrong, I just didn't feel wrong about it. Now I do.
- splicer 14y agoThe purpose of using a hash is just to avoid running out of disk space. With enough disk space, you don't even need to hash/delete files.
- mseebach 14y agoThe problem isn't that the program runs for a long time, it's that "likely" doesn't cut it. It would have to be deterministic to live up to even the most informal definition of "decompress".