Re: factorization an NP problem (don't see it)-



oferlock@xxxxxxxxx wrote:

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?



First of all: do you mean NP in the number of digits of m? or NP in the magnitude of m itself?

Think about exp(x) = 1 + x/1 + (x/1)(x/2) + (x/1)(x/2)(x/3) + ...

as an example of how the sum of a series of polynomials is itself NP, i.e. no longer of the order of growth of a polynomial of any degree.
A similar observation could be applicable in your problem.

IHTH: Johan E. Mebius



.