I just calcualted how much time does it need to crack puzzle 66 by bruteforcing
 
The answer is: Infinity OR almost Impossible.

What's insane is, even if someone managed to get 100,000 GPUs, you still would need 3.5 Months to go through all the range. Not to mention electricity cost of the 100,000 GPUs. I think this puzzle is still infeasible. It's worth to mine better than trying to solve this.

What's feasible though is puzzle 125, because of its public key.