You can be linear in the bit length of the input number, but exponential in the magnitude.

This is a common thing in complexity, and I think even the abstract says it is talking about “length n” and not “magnitude n”