GCD is easy. Factoring is comparatively hard, though there are algorithms much better than brute force.

I would have said that complexity theory is the place where we often have simple descriptions of hard- or impossible- to compute values. The busy-beaver function, say.