After reading this post An NP-complete variant of factoring. I come up with a question.
To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides an given number n and $p$ is between a given interval $l \leq $p$ \leq u$. The variant of the factoring problem (VF) ask for a number $p$ that divides an given number n and $p$ is in the interval $l \leq $p$ \leq u$, but not necessarily needs to be prime. So while (F) is not believed to be NP-complete, (VF) is.
But couldn't you solve (VF) with polynominal many oracle calls to (F), by first getting all prime divisors of n. (This list, lets call it l, has at most $log_2(n)$ many entries) Then calculate all subset products of $l$. An upper bound for how many this could be, would be given by the number of ways of choosing $i$ many elements from $l$, for $i = 0$ to $log_2(n)$. So $\sum_{i = 0}^{log_2(n)} \binom{log_2(n)}{i} = 2^{log_2(n)} = n$. So there also polynominal many products, which needs to be checked if they are between $l$ and $u$.
Wouldn't this make Factoring also NP-complete?
