# Why is this problem not in $P$?

I have been trying to figure out why this problem is supposedly not in $$P$$. Eager to learn where my reasoning is wrong!

Problem:

Given a pair of integers ($$n$$, $$m$$) in binary, does there exist $$2 \leq k \leq m$$ such that $$k$$ divides $$n$$?

Reasoning:

In order to find a potential $$k$$ we need to loop over all numbers from 2 to $$m$$, which takes a linear time. For each number we need to perform the modulo computation, which takes a constant time. Hence, in total we require a linear time to loop over all possible candidates, which is within the poly-time and hence this problem is in $$P$$.

• For $m=n$ this is primality testing and it is in P, though. Of course, your brute force algorithm does not solve it in polynomial time. Otherwise I'd think it's an open problem, not proven to not be in P. Dec 13, 2023 at 11:21
• In this case, note that $m=2^l$ where $l$ is the length of the input in binary. As you can see, $m$ is exponential, so your algorithm takes exponential time in the worst case. Dec 13, 2023 at 11:58

Because $$n$$ and $$m$$ are given in binary, the length of the input is $$O(\log n + \log m)$$. Looping from 2 to $$m$$ will in this case require time not linear, but exponential in the size of the input.