Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $2^k\pm1$ where input is now $k$ whose representation length in number of bits is now logarithm of number of bits to represent $2^k\pm1$.
For these numbers since factors are witnesses, the decision problem related to computing the factors is in $NEXP$ (in fact in $UEXP$). Is decision problem of factorization of these numbers in $EXP$? For that matter is computing factors in $PSPACE$ (essentially polynomial time but computation in parallel over exponential number of machines)?
