For "strong keys" in certain forms of encryption you'd like to create 2 "random" primes that are of about equal length. This greatly reduces the space.
Given a pile of machines it seems that a feasible attack would be to "randomly" generate primes clustered around the 1/2 length size and write them to disk. That's a lot of primes but we have plenty of time, plenty of disk space, and a rather smaller search space based on our assumption.
Next you create "rainbow tables" by multiplying the resulting primes, keeping only a small portion of the result such as the first 16 bits, and the two primes used to create the key.
Now, given a key to break, you index it by using the first 16 bits as a hash key, finding a "bucket" of prime products that result in the same 16 bits.
For each entry in the bucket the question is "if I recreate the product of the primes, does it match the key?"
It is "brute force" on a large scale but I'd bet that certain agencies can create these rainbow tables and that with sufficient effort such tables could "break" any crypto key you're likely to generate using commodity hardware and software.
Just a thought...