Why isn't DIV necessarily in P? [duplicate]

Question

In my formal languages class, we discussed DIV, defined as following:

$\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 < d \leq b$ }\}$

($\langle\cdot\rangle$ means encoded, let's say as binary)

We were told that it isn't known whether DIV is in P and were tasked to prove it was in NP. I naively and mistakenly assumed that DIV was in P because of the following algorithm:

   On input <a,b>
   For all 1<d<=b
       check if d divides a.
       If so, accept.
   reject.

I thought that this algorithm would run in polynomial time because we do $b$ many divisions at worst. Division is polynomial time, therefore, $b$ many divisions is also polynomial time. (also note, $b < a$, or DIV is trivially true, where $d = a$).

However, i was told that this algorithm is not polynomial time with respect to the input. I don't really understand this part. Something along the lines of since $a$ and $b$ are encoded in binary, the input is of order $O(\log n)$. And that means our b many divisions is actually $O(b) \cdot O(\text{divisions})$, and that $O(b)$ is $O(2^{\log b})$. However, isn't $2^{\text{log base $2$ of $b$}}$ the same as $b$? How is that not polynomial time?

Answer 1

When we say that an algorithm runs in polynomial time, we mean polynomial in the length of the input to the algorithm, i.e., the number of bits needed to represent the input. Suppose both $a$ and $b$ are at most $n$; then the pair $\langle a,b\rangle$ takes $\lg n$ bits to represent. So, an algorithm whose running time is $O(n)$ takes exponential time (exponential in $\lg n$). In particular, your algorithm is an exponential time algorithm.

The problem DIV is basically equivalent to the integer factoring problem. It is an open question whether there exists any polynomial-time algorithm for it, but many believe that there probably is no polynomial time algorithm for it.