# On variant of integer factorization

In the post on site cstheory.stackexchange on whether a variant of integer factorization $$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ integer}\mbox{ } m \in \{a, \ldots, b\}\mbox{ }\mathsf{ such}\mbox{ }\mathsf{that}\mbox{ }m | n\}$$ is $\mathsf{NP}$ complete, it is clear that difference $b-a$ can neither be too small nor too big for the problem to remain $\mathsf{NP}$ complete under Cramér's conjecture.

What is the possible range of difference $b-a$ under which the problem remains $\mathsf{NP}$ complete under Cramér's conjecture?

Note in this problem $m$ need not be prime which makes the problem combinatorial rather than arithmetical

• I don't understand - it is not even known that factorization is NP-complete. – Igor Rivin Nov 1 '15 at 22:13
• This is a variant of factorization $m$ need not be prime. – T.... Nov 1 '15 at 22:40
• @IgorRivin Check out answer and comments in link included in post – T.... Nov 2 '15 at 0:24
• Factorization is factorization. It's still arithmetical, not combinatorial. – Gerry Myerson Nov 2 '15 at 0:28
• no this is not arithmetical at all, you can factorize into primes which are small but $m$ needs to be pieced together (this last step is not at all arithmetical) into a factor which is exponential in compared to any of prime factors – T.... Nov 2 '15 at 0:54