I wonder if you wanted to communicate to aliens in the most compact way possible, that you had computational power, would it be a good idea to send a hashcash preimage.

The problem is that all our hash functions are arbitrary constructs, so wouldn't be recognized of course. Possible solution: transmit the order of the finite field N, then use the discrete log over that finite field as your "hash function"; send preimage x of g^x = ultra low value.

Choice of g: just the smallest generator?