With brute force I would need to use 2^56 different private keys to generate 2^56 public keys. Too much time. But If I knew only the address and not the public key, that would be the only way.
Could you briefly describe what this process would be like, if you can? In terms of possible time to generate, and space to save the results.
What I think you're saying, if I understand it, is that you would generate all 56-bit private keys, for unsigned integers that would be 2^56 - 1 private keys, or 72,057,594,037,927,935. Wow, 72 quadrillion, 57 trillion and so on. Then generate a public key for each of those 72 quadrillion+ private keys.
But, if you don't know what the private key is, to solve a puzzle, this would be a fairly insane process of using a lookup table perhaps. Suppose only compressed public keys are computed for each private key, then compute sha256(pubkey) -> ripemd160( sha256(pubkey) ) for the Hash160 of the address, or just go a step further and use the Base58Check address list from the public keys.
So in other words, the only method here is to have a huge lookup table, and if you have a massive RDBMS for it, then select privkey from lookup_table where (hash160 || base58check) = target_address, and hope you get a hit.
I suppose there would be a better way to implement a lookup table, like cutting some bits off the hash160 or base58check address, then do a lookup on priv_key where first 64 bits of hash160 = first 64 bits of target hash160, and maybe one will pop out. Still, a massive operation. Assuming billions of keys per second, that will still take a heck of a long time, not to mention the computation of the public key and other operations from each of the private keys, and the space needed to store the lookup table or database.