I'm trying to show that the language $\{(m,n) | m \space \text{has exactly} \space n \space \text{divisors}\}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime factors of $m.$
2) Verify that $\prod i(di+1) = n.$
The problem is that I can't find a way to factorize in polynomial time (in the input) the number $m.$
If stage $1$ takes m steps then it would be $m = 2^{\log (m)}$ and the whole algorithm would run in exponential time.
How can I factorize a number in binary in polynomial time (polynomial in the input)?