There's exists a polynomial-time algorithm to factor integers, Shor's algorithm, which runs in $O[N^2 \log[N] \log\log[N]]$ time, where $N$ is the number of digits of the integer you want to factor.
I think that using a non-deterministic Turing machine you can also factor integers in polynomial time.
Regarding your question, I suspect this may be somehow related to exponential growth: in a (say, binary) tree, the number of paths growths exponentially as you add more levels, so the difficultly of finding the "correct path" seems to grow exponentially (assuming there's no structure to exploit), but verifying that any given path is the "correct one" is linear (in the height of the tree). (But verifying all paths is again exponential. Think of "verifying some path" a single piece of a puzzle, and of "verifying all paths" as the entire puzzle.)
Something similar happens in the infinite (think of the Stern-Brocot tree): the set of all finite paths in an infinite binary tree is (isomorphic to) the rationals ${\bf Q}$, but the set of all infinite paths is (isomorphic to) the irrationals, so your cardinality has grown exponentially, from $\aleph_0$ to $2^{\aleph_0}$.
For integers, as you add digits, the number of integers grows exponentially too.