Does 'subexponential algorithm' refer to input or number of bits used to represent input? When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N?  Consider the following: trial division for integer factorization (i.e. try all numbers less than $\sqrt N$) is subexponential in terms of N.  

Note: here I'm using the definition of 'subexponential' to be $2^{O(n^\epsilon)}$ for some $\epsilon &lt; 1$.

That is it takes $2^{\log_2 \sqrt N}$ steps to factor N.  This is obviously subexponential in terms of N.  However, in terms of the number of bits B needed to represent N this is $2^{\frac B 2}$ which is not subexponential in terms of B.

So would trial division be considered subexponential or not?  Or would it be considered both depending on whether you're referring to N or B?
It refers to the number of bits to represent N.  More generally, the complexity of a problem is normally taken to be a function of the length of the input (the number of bits needed to represent the input).

Trial division is exponential: its running time is $O(N^{1/2})$, i.e., $O(2^{B/2})$ where $B=\lg N$ is the length of the input in bits.  That's an exponential function (of $B$).  See Are there subexponential-time algorithms for NP-complete problems?.