factorization an NP problem (don't see it)

factorization as a decision problem : given a composite integer m and
k<m, does m have a non-trivial factor less than k?
this is an NP problem, since given an integer (witness), w, such that w
<= k, we can check by long-division if w is a factor of m. My dilemma :
if this can be done for all intergers upto k in polynomial time O(n^t),
then we can check each of the integers upto k and that's only a factor
of n (at most) slowdown. i.e, still O(n^(t+1)). Where is the catch?

.

Relevant Pages

  • Re: reducing the factorization decision problem to SAT?
    ... It's obviously possible to reduce an NP decision problem to SAT using ... (Or any other decision problem that the factorization ... That is, the output of the whole circuit is the output of this AND gate, ... something that decides SAT without providing satisfying assignments, ...
    (comp.theory)
  • reducing the factorization decision problem to SAT?
    ... It's obviously possible to reduce an NP decision problem to SAT using ... Cook-Levin's mapping, but how does one do it in an "intelligible," ... simple way in practice for integer factorization? ... (Or any other decision problem that the factorization ...
    (comp.theory)