I thought of using hashes too, but then I realized that after thousands of years, the program is only going to output a collision, and not the original data.

Checking the first and last few bits reduces the number of collisions, but there are still 2^unchecked_bits/2^160 cyphers which map to the same hash. You could store the number of collisions to skip along with the hash, but that number will be about (unchecked_bits - 161) bits long, so that won't work either.